This is a Leetcode problem:



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


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.       

Here is an example of an input/output:

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



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
                    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)

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.

  • 1
    \$\begingroup\$ Umm... Why the downvote? Is anything wrong with the question? \$\endgroup\$ – Justin May 23 '19 at 14:36
  • \$\begingroup\$ I didn't downvote but I'm tempted to... a short description about each solution like why you have implemented it that way would be great. Do you think any of them is better, prettier etc... what were the reasons you've decided to take either of the approaches? \$\endgroup\$ – t3chb0t May 23 '19 at 16:26

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
| improve this answer | |

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
        return min(1+jump(nums[m:]) for m in range(1,min(len(nums),nums[0]+1)))
| improve this answer | |

Your Answer

