Katkat
Back

Can You Reach the Last Index?

WaymoSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to determine reachability in a sequence using greedy strategy or dynamic programming to optimize pathfinding.

Problem Statement

You are given an array of non-negative integers jumps, where each element jumps[i] represents the maximum distance you can jump forward from index i.

Starting at index 0, determine if you can reach the last index of the array.

Function Signature

def can_reach_end(jumps: List[int]) -> bool:

Constraints

  • 1 <= jumps.length <= 10^4
  • 0 <= jumps[i] <= 10^5

Examples

Example 1:

  • Input: jumps = [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: jumps = [3, 2, 1, 0, 4]
  • Output: False
  • Explanation: You will always arrive at index 3, which has a jump capacity of 0, preventing further movement.

Edge Cases

  • Single element array (e.g., [0]): Should return True.
  • Array with a zero early on: Check if the jump capacity before the zero is sufficient to bypass it.

Hints

Hint 1

Consider tracking the furthest index you can reach at any given point during the traversal.

Hint 2

You do not need to know which path to take, only whether the maximum possible reach is ever greater than or equal to the last index.

Hint 3

Iterate through the array and update a variable `max_reach` as `max(max_reach, i + jumps[i])`; if you encounter an index `i` where `i > max_reach`, you are stuck.

Follow-up questions

  • How would you modify your solution if you needed to return the minimum number of jumps required to reach the last index?
  • What is the time and space complexity of your approach? Can it be optimized further?
  • How does your algorithm behave if the array contains negative numbers (though not allowed here) or if the jump could be directed backwards?