Skip to main content

Greedy

common questions

Jump Game​

Source

Video explanation by NeetCode.

Solution 1: Greedy Approach (Preferred Solution)​

  • Set variable goal from end of array.
  • Move goal variable from reverse order of the array until 0 is reached.
def canJump(self, nums):
  goal = len(nums) - 1
  for i in range(len(nums) - 2, -1, -1):
    if nums[i] >= (goal - i): # if can jump to goal from i
      goal = i # update goal to i
  return goal == 0

Time Complexity: O(n) for one-pass of the nums array.

Space Complexity: O(1).


Solution 2: Dynamic Programming​

Source

Explanation by LeetCode discussions.

def canJump(self, nums):
  dp = [False] * len(nums)
  dp[-1] = True
  for i in range(len(nums)-2, -1, -1):
    for j in range(i + 1, min(len(nums), i + nums[i] + 1)): # Check all possible jumps from i
      if dp[j]:
        dp[i] = True
        break
  return dp[0]

Time Complexity: O(N^2) due to double for-loops for dynamic programming solution.

Space Complexity: O(N) for size of dp.