Crossing the Stepping Stones

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Crossing the Stepping Stones

You start on the first stone of a river crossing. Each entry in nums is the maximum number of stones you may jump forward from that position.

Return True if you can reach the last stone, otherwise False.

def can_jump(nums):
    pass

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-25 mins
🛠️ Topics: Arrays, Greedy Algorithms, Reachability

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: Does the value at each stone mean we must jump exactly that far?
- A: No. Each value is the maximum jump length from that stone; any shorter forward jump (including a jump of 1) is allowed.
Q: Where do we start, and what counts as success?
- A: We always start on the first stone (index 0), and we succeed if we can land on or pass the last stone (index len(nums) - 1).
Q: What happens if we land on a stone with value 0?
- A: We cannot jump forward from it. If every path forces us onto such a stone before the end, the crossing is impossible and we return False.

HAPPY CASE
Input: nums = [2, 3, 1, 1, 4]
Output: True
Explanation: Jump 1 stone from index 0 to index 1, then 3 stones from index 1 to index 4, the last stone.

Input: nums = [3, 2, 1, 0, 4]
Output: False
Explanation: No matter what, we always land on index 3. Its maximum jump is 0, so we can never reach the last stone.

EDGE CASE
Input: nums = [0]
Output: True
Explanation: There is only one stone, and we are already standing on it, so the crossing is trivially complete.

Input: nums = [1, 0, 1]
Output: False
Explanation: The only move from index 0 is to index 1, which has a jump value of 0, so we are stranded mid-river.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Reachability in an Array, we can consider the following approaches:

Greedy: Sweep left to right while tracking the farthest stone reachable so far. If we ever stand on a stone beyond that reach, the crossing fails; if the reach covers the last stone, it succeeds.
Dynamic Programming: Mark each stone as reachable/unreachable based on earlier stones. This works but costs O(N^2) time, so the greedy sweep is preferred.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Walk across the stones from left to right, maintaining a single variable farthest: the highest index we know we can reach using the stones seen so far. At each stone i, if i is beyond farthest, the stone is unreachable and we return False. Otherwise extend farthest to max(farthest, i + nums[i]). If farthest ever reaches the last index, return True.

1) Initialize `farthest = 0` (from the first stone, we can reach at least index 0).
2) For each index `i` and jump value `jump` in `nums`:
   a) If `i > farthest`, we can never stand on stone `i`. Return False.
   b) Update `farthest = max(farthest, i + jump)`.
   c) If `farthest >= len(nums) - 1`, the last stone is within reach. Return True.
3) If the loop finishes, every stone (including the last) was reachable. Return True.

⚠️ Common Mistakes

Treating each value as a forced jump distance instead of a maximum, which wrongly rules out shorter hops.
Simulating every possible jump path recursively without memoization, leading to exponential time.
Forgetting the single-stone case [0], where no jump is needed at all.
Checking i >= farthest instead of i > farthest, which wrongly fails when we are standing exactly at the edge of our reach.

4: I-mplement

Implement the code to solve the algorithm.

def can_jump(nums):
    farthest = 0  # Highest index reachable with the stones seen so far
    for i, jump in enumerate(nums):
        if i > farthest:
            return False  # Stone i is beyond our reach, so we can never stand on it
        farthest = max(farthest, i + jump)  # Extend our reach from stone i
        if farthest >= len(nums) - 1:
            return True  # The last stone is within reach
    return True

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input: nums = [2, 3, 1, 1, 4]
- i = 0: farthest = max(0, 0 + 2) = 2
- i = 1: farthest = max(2, 1 + 3) = 4, and 4 >= 4 (last index), so return True.
- Output: True
Input: nums = [3, 2, 1, 0, 4]
- i = 0: farthest = max(0, 0 + 3) = 3
- i = 1: farthest = max(3, 1 + 2) = 3
- i = 2: farthest = max(3, 2 + 1) = 3
- i = 3: farthest = max(3, 3 + 0) = 3
- i = 4: 4 > farthest (3), so stone 4 is unreachable. Return False.
- Output: False
Input: nums = [0]
- i = 0: farthest = 0, and 0 >= 0 (last index), so return True.
- Output: True

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of stones in nums.

Time Complexity: O(N) because we make a single pass over the stones, doing constant work at each one.
Space Complexity: O(1) because we only track the single farthest variable regardless of input size.

Uh oh!

Crossing the Stepping Stones