algoadvance

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which means you can never reach the last index.

Clarifying Questions

  1. What should we return if the input array is empty?
    • Since you’re always starting at the first index, an empty array would not occur in a valid input.
  2. What should we do if the array contains only one element?
    • If the array has only one element, you’re already at the last index, so you should return true.

Strategy

To solve the problem, we can use a greedy approach. We will keep track of the furthest index we can reach while iterating through the array. If at any point, we find that our current position is beyond the furthest reach so far, we can conclude that reaching the last index is impossible.

Here is the step-by-step strategy:

  1. Initialize a variable max_reach to 0, which keeps track of the maximum index we can reach.
  2. Iterate over each index i in the array.
  3. At each index, if i is greater than max_reach, return false (because we can’t move forward from here).
  4. Update max_reach to be the maximum of its current value or i + nums[i].
  5. After the loop, if max_reach is greater than or equal to the last index of the array, return true.

Code

def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return max_reach >= len(nums) - 1

Time Complexity

The time complexity of the solution is O(n), where n is the number of elements in the input array nums. This is because we make a single pass through the array.

The space complexity is O(1) since we are using a constant amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com