Jump Game - Leetcode

Question

Below is my solution for the LeetCode Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]

Output: true

This is my solution. It is correct but timed out the LeetCode code-checker for an array of 25000 elements.

Please can someone help me improve this code.

It seems to have a time complexity of O(N^2) and a space complexity of O(N). I cannot work out a method faster than O(N^2).

def function(nums):
    if len(nums) == 1:
        return True
    output = [0] * len(nums)
    last_index = len(nums) - 1
    output[0] = 1

    for index, number in enumerate(nums):
        if output[index] == 0:
            continue
        if output[index] == 1:
            stop_at = min(last_index, index + number)
            for i in range(index, stop_at + 1):
                output[i] = 1
        if output[last_index] == 1:
            return True
    return False


if __name__ == "__main__":
    nums = [3,2,1,0,4]
    output = function(nums)
    print(output)

Answer 1

O(n) Solution

You don't need to keep track of all the places you can reach. You only need to know what is the highest index you can reach, because you can reach any lower index by choosing a shorter jump. Scan the list from 0 to the end keeping track of the maximum reachable index. If you ever reach an index greater than the maximum reachable index, you've hit a block and can't reach the end.

For example, for a jump list = [3,2,1,0,4]. Starting at index 0, we can reach any index up to 0 + 3 = 3. From index 1 we can reach 1 + 2 = 3. From 2, we can reach 2+1 = 3. From index 3, we can reach 3 + 0 = 3. So far the maximum reachable index is 3. So when we reach index 4, 4 > 3 so index 4 is unreachable and we can't get to the end.

def canjump(nums):
    maximum_reachable_index = 0

    for index, max_jump in enumerate(nums):
        #print(f"{index}", end=' ')
        if index > maximum_reachable_index:
            #print(f"> {maximum_reachable_index} and is unreachable.")
            return False

        #print(f"+ {max_jump} => {index + max_jump} : {maximum_reachable_index} ")
        maximum_reachable_index = max(index + max_jump, maximum_reachable_index)

    return True

Uncomment the print statements to see how it works.

Answer 2

Coding style

Your code passes the PEP8 online check without errors or warnings, that's great.

Naming

The function name function is pretty non-descriptive. The Leetcode template uses canJump, but according to Python PEP 8

Function names should be lowercase, with words separated by underscores as necessary to improve readability.

that would be can_jump. Your output array stores which positions are reachable from the initial position, a better name might be reachable. The index is the current position, and number is the jump width at that position.

Coding improvements

The output/reachable array should be an array of boolean values instead of integers. The test

if output[index] == 0:
    continue

is not needed, and the test

if output[last_index] == 1:
    return True

needs only to be done at reachable positions. Summarizing the suggestions so far, we have

def can_jump(nums):
    if len(nums) == 1:
        return True
    reachable = [False] * len(nums)
    last_pos = len(nums) - 1
    reachable[0] = True

    for pos, jump_width in enumerate(nums):
        if reachable[pos]:
            stop_at = min(last_pos, pos + jump_width)
            for i in range(pos, stop_at + 1):
                reachable[i] = True
            if reachable[last_pos]:
                return True
    return False

Performance improvements

The crucial observation is that the list of reachable positions is always an interval (from position 0 to some maximal reachable position). This interval can be described by a single integer variable

last_reachable = 0

which is updated while traversing the array. I won't deprive you of the satisfaction to program the solution yourself, therefore I'll mention only the general idea. While enumerating the array:

• If the current position is not reachable then return False.
• Otherwise, update last_reachable with the maximum of its current value and the greatest position reachable from the current position.
• Return True as soon as the final position turns out to be reachable.

This approach needs less memory (no additional array), and only a simple loop instead of nested loops.