Python program for Jump game II

Question

This is a Leetcode problem:

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.

Your goal is to reach the last index in the minimum number of jumps.

Note:

You can assume that you can always reach the last index.

Here is my first solution to this problem:

def jump(nums):
    n = len(nums)
    curr_far = min(nums[0], n - 1)
    next_far = 0
    step = 0
    for i in range(n):
        if i <= curr_far:
            if next_far < i + nums[i]:
                next_far = min(i + nums[i], n - 1)
            if i == curr_far and curr_far != 0:
                curr_far = next_far
                step += 1

    return step

nums = #Enter a list.       
print(jump(nums))

Here is an example of an input/output:

nums = [2,3,1,1,4]
>>> 2

The minimum number of jumps to reach the last index is 2.

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Here is my second solution to this problem:

class Solution:

    def __init__(self, nums):
        self.nums = nums

    def jump(self, nums):
        if not nums or len(nums) == 1:
            return 0

        curr = 0
        count = 0
        while(curr < len(nums)):
            maxReach = -1
            index = 0
            for i in range(1, nums[curr] + 1):
                if curr + i >= len(nums) - 1:
                    return count + 1
                else:
                    if nums[curr + i] + i > maxReach:
                        maxReach = nums[curr + i] + i
                        index = curr + i
            curr = index
            count += 1

nums = #Enter a list.           
game = Solution(nums)
print(game.jump(nums))

Input/output - Same as above.

So, I would like to have a code review for the efficiency of both the programs.

Any help would be highly appreciated.

Answer 1

Improving the first solution

I like the first solution better, because I find it easier to understand how it works, and it's shorter.

It can be a bit simpler. The condition if i <= curr_far: is unnecessary and can be safely dropped.

Instead of iterating over a range of indexes, I nice trick is to use enumerate, like this:

for index, value in enumerate(nums):

This way, instead of nums[index] in the loop body, you can use value directly.

Another code smell is the condition if i == curr_far and curr_far != 0 executed in every iteration of the loop, even though curr_far != 0 will only be false for the first iteration, otherwise always true.

I didn't like most of the variable names...

• Instead of step, I would find jumps more natural
• Instead of curr_far and next_far, I would find reach and next_reach more intuitive

All in all, I would write like this instead:

class Solution(object):
    def jump(self, nums):
        end = len(nums) - 1
        if not end:
            return 0

        reach = 0
        next_reach = 0
        jumps = 0
        for pos, value in enumerate(nums):
            if next_reach < pos + value:
                next_reach = pos + value
                if next_reach >= end:
                    return jumps + 1

            if pos == reach:
                reach = next_reach
                jumps += 1

Issues with the second solution

• Looks more complex than the first, and I think unnecessarily so
• The __init__ method is completely unnecessary
• The outer parentheses are unnecessary in while(curr < len(nums)):
• The convention for the naming style of variables in Python is snake_case instead of camelCase

Answer 2

This problem lends itself to a recursive solution. You want a recursive algorithm that

• returns 0 if the length of the input array nums is 1

• otherwise creates a new input array for a jump of size from 1 to nums[0], calculates the jumps for the new input array, adds 1, and returns the minimum

In Python this would be:

def jump(nums):
    if len(nums)<=1:
        return 0
    else:
        return min(1+jump(nums[m:]) for m in range(1,min(len(nums),nums[0]+1)))