LeetCode #55: Jump Game

LeetCode Solutions

https://leetcode.com/problems/jump-game/

We can solve this problem using a greedy approach. We can keep track of the furthest index that can be reached at any point in time. While traversing through the array, if we come across an index that is beyond the furthest index we can reach, then we return False as it is not possible to reach the end of the array. If we reach the end of the array without encountering such an index, then we return True.

  1. We initialize the furthest index to 0 as we can start at the beginning of the array.
  2. We traverse through the array and for each index, we check if it can be reached from the furthest index.
  3. If it can be reached, we update the furthest index by adding the maximum jump length from that index.
  4. If at any point, we encounter an index that is beyond the furthest index, we return False as it is not possible to reach the end of the array.
  5. If we reach the end of the array without encountering such an index, we return True.

Consider the input array nums = [2,3,1,1,4].

Initially, furthest = 0.

  • At index 0, the maximum jump length is 2. Therefore, furthest becomes 2.
  • At index 1, the maximum jump length is 3. Therefore, furthest becomes 4.
  • At index 2, the maximum jump length is 1. As 2 + 1 < 4, we can’t reach this index, and we return False.
  • If we reached the end of the array without returning False, we would return True.

Here is the solution in python3:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        furthest = 0
        for ind, val in enumerate(nums):
            if ind > furthest:
                return False
            if val + ind > furthest:
                furthest = val + ind

        return True

Time complexity

The time complexity of this solution is O(n), where n is the length of the input array. This is because we iterate through the array only once, checking if we can reach the end or not. At each index, we update the furthest point we can reach, which is a constant time operation. Thus, the time complexity is linear with respect to the size of the input.

Space complexity

The space complexity of this solution is O(1), which means that we use a constant amount of extra space that does not depend on the size of the input array. We only use a single variable furthest to keep track of the furthest index we can reach. Since we do not store any extra data, the space complexity is constant.