Jump Game | LeetCode | Solution Explained

55. Jump Game on LeetCode is a medium problem. I discuss the iterative dp solution as well as the greedy solutions. Problem link.

Iterative DP


  • an index i can jump to max index i+nums[i]
  • alternatively, it can jump to all i+k for k in [1, nums[i]]
  • for i in [0, n):
    • if we can’t reach i, we can just skip considering it
    • if we can reach i, we can reach all i+ks
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False]*n
        dp[0] = True
        for i in range(n):
            if not dp[i]: continue #if False, we have no use for it
            for k in range(1, nums[i]+1):
                if i+k == n-1: return True
                if i+k <= n - 1: dp[i+k] = dp[i]
        return dp[n-1]
  • Time: O(N*K)
  • Space: O(N)

O(1) Space Solution


  • an index i can jump to max index i+nums[i]
  • we can keep a track of the max_index we can jump to
  • as we iterate over the elements, if i > max_index, this means that the index i is unreachable
  • so, any index after it is also unreachable – so, we return False
  • else max_index = max(max_index, i+nums[i])
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_index = 0
        for i, x in enumeratenums):
            # we have a gap, the current index cant be reached from the max_index reachable
            if i > max_index: return False 
            max_index = max(max_index, i+x)
        return True
  • Time: O(N)
  • Space: O(1)


Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.


    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.