Crack the Backend

Problem Statement

You are given an integer array nums. Initially you are at the first index. nums[i] represents the maximum jump length from index i (you can jump to any index from i to i + nums[i] inclusive). Return true if you can reach the last index, otherwise false.

You start at index 0 and can jump at most nums[i] steps from index i.
We only need to know reachability of the last index, not the minimum number of jumps.

Key Observations

We can greedily track the farthest index we can reach so far. If we are at step i and i is within the current farthest, we can reach i; then from i we can reach up to i + nums[i]. So we update farthest = max(farthest, i + nums[i]).
If at any step i we have i > farthest, it means we cannot reach i (and thus cannot reach the end), so return false. If we ever have farthest >= n-1, we can reach the last index — return true.
One pass from left to right is enough.

Approach

High-level: Maintain farthest = the farthest index we can reach. For each i from 0 to n-1: if i > farthest we cannot proceed, return false; else update farthest = max(farthest, i + nums[i]). If farthest >= n-1, return true. After the loop, return true if we reached the end.

Steps:

farthest = 0. For i = 0..n-1: if i > farthest return false. farthest = max(farthest, i + nums[i]). If farthest >= n-1 return true.
Return true (we reached the last index).

Implementation

Java

public boolean canJump(int[] nums) {
    int far = 0;

    for (int i = 0; i < nums.length; i++) {
        if (i > far) {
            return false;
        }

        far = Math.max(far, i + nums[i]);
    }

    return true;
}

Test Cases

Example 1

Input

nums = [2,3,1,1,4]

Expected

true

Explanation

Jump 1, then 3.

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.