Determine reachability and minimum jumps
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array of non-negative integers nums of length n, where nums[i] is the maximum number of steps you can move forward from index i:
(
1) Determine whether you can reach index n-1 starting from index 0.
(
2) If reachable, compute the minimum number of jumps required to reach index n-1. Aim for an O(n) time, O(
1) extra space solution if possible. Explain the algorithm, prove its correctness, analyze time/space complexity, and discuss edge cases (e.g., zeros that block progress, n=1, very large jump values, and cases where the last index is unreachable).
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine reachability and minimum jumps states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Jump Game: Reachability
Given an array of non-negative integers `nums` of length `n`, where `nums[i]` is the maximum number of steps you can move forward from index `i`, determine whether you can reach the last index `n-1` starting from index `0`. Return `true` if reachable, `false` otherwise.
Aim for an O(n) time, O(1) extra space solution.
**Approach (greedy):** Track the farthest index reachable so far. Scan left to right; at each index `i`, if `i` is already beyond the farthest reachable index, you are stuck and can never reach the end, so return `false`. Otherwise update `farthest = max(farthest, i + nums[i])`. If `farthest` ever reaches or passes `n-1`, return `true`. By convention an array of length 0 or 1 is trivially reachable (you are already at the last index).
**Correctness:** Every index up to `farthest` is reachable (induction: index 0 is reachable; if index `i <= farthest` is reachable then so is every index in `[i, i+nums[i]]`). If the scan never gets stranded (`i > farthest`), the union of these intervals covers `[0, farthest]`, and once `farthest >= n-1` the last index lies in a covered interval. Conversely, getting stranded means a hard gap of zeros blocks all paths.
Constraints
- 1 <= n <= 10^4 (problem also defines the empty array as trivially reachable)
- 0 <= nums[i] <= 10^5
- All values are non-negative integers
Examples
Input: ([2, 3, 1, 1, 4],)
Expected Output: True
Explanation: From index 0 (value 2) jump to index 1, which can reach index 4. Reachable.
Input: ([3, 2, 1, 0, 4],)
Expected Output: False
Explanation: The best you can do lands on index 3 (value 0), which blocks all progress; index 4 is unreachable.
Hints
- You do not need to track every path. Track a single number: the farthest index reachable so far.
- Scan left to right. If the current index i ever exceeds the farthest reachable index, you are stranded behind a wall of zeros and can never reach the end.
- At each index update farthest = max(farthest, i + nums[i]); as soon as farthest >= n-1 you can stop early and return true.
- Edge cases: n == 1 (already at the last index, return true) and a leading or interior run of zeros that the farthest reach cannot clear.
Jump Game II: Minimum Jumps
Given an array of non-negative integers `nums` of length `n`, where `nums[i]` is the maximum number of steps you can move forward from index `i`, compute the minimum number of jumps required to reach the last index `n-1` starting from index `0`. If the last index is unreachable, return `-1`.
Aim for an O(n) time, O(1) extra space solution.
**Approach (greedy / BFS-by-levels):** Treat the array as a layered BFS. Maintain `cur_end` (the farthest index reachable using the jumps taken so far) and `farthest` (the farthest index reachable using one more jump from anywhere in the current layer). Scan `i` from `0` to `n-2`. If `i` ever exceeds `farthest`, the end is unreachable, return `-1`. Update `farthest = max(farthest, i + nums[i])`. When `i == cur_end`, the current jump 'layer' is exhausted, so increment the jump count and advance `cur_end = farthest`; if `cur_end >= n-1` you can return the count immediately.
**Correctness:** Each jump-count increment corresponds to expanding to the next BFS frontier, which by definition is the minimal number of jumps (BFS finds shortest paths in an unweighted reachability graph). We never overcount because we only increment when we are forced to leave the current frontier. By convention an array of length 0 or 1 needs 0 jumps.
Constraints
- 1 <= n <= 10^4 (problem also defines the empty array as needing 0 jumps)
- 0 <= nums[i] <= 10^5
- All values are non-negative integers; return -1 when the last index cannot be reached
Examples
Input: ([2, 3, 1, 1, 4],)
Expected Output: 2
Explanation: Jump 0->1 (value 3), then 1->4. Two jumps is minimal.
Input: ([2, 3, 0, 1, 4],)
Expected Output: 2
Explanation: Jump 0->1, then 1->4, skipping the zero at index 2. Two jumps.
Hints
- Think of it as BFS in layers: every index reachable in k jumps forms one layer.
- Track cur_end (farthest reachable with the jumps taken so far) and farthest (farthest reachable with one more jump from the current layer).
- Only increment the jump count when i reaches cur_end — that is the moment you are forced to spend another jump to advance the frontier.
- Guard against unreachable inputs: if i ever exceeds farthest you are stranded, return -1. Also handle n == 1 (0 jumps) up front.