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

Logic

  • 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

Logic

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

References

    Leave a Reply

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