How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Waymo.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Waymo during technical interviews.

Can You Reach the Last Index? | Waymo Coding Question

Can You Reach the Last Index?

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an array `nums` of non-negative integers. You start at index `0`. From index `i`, you may jump to any index `j` such that `i < j <= i + nums[i]`. Return `true` if there exists a sequence of jumps that reaches the last index of the array, and `false` otherwise. Example: - Input: `nums = [2, 3, 1, 0, 4]` - Output: `true` Explain the approach you would use and its time complexity.

Quick Answer: This question evaluates a candidate's understanding of array traversal and reachability in sequences of jumps, along with the ability to reason about algorithmic time and space complexity.

You are given an array `nums` of non-negative integers. You start at index `0`. From index `i`, you may jump to any index `j` such that `i < j <= i + nums[i]`. Return `true` if there exists a sequence of jumps that reaches the last index of the array, and `false` otherwise. Example: - Input: `nums = [2, 3, 1, 0, 4]` - Output: `true` (jump 0 -> 1 -> 4, or 0 -> 2 -> 4) Note: `nums[i] == 0` means you cannot jump forward from index `i`. An array of length 1 trivially reaches the last index.

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5
An array of length 1 returns true (already at the last index)

Examples

Input: ([2, 3, 1, 0, 4],)

Expected Output: True

Explanation: Jump 0 -> 2 (nums[0]=2) then 2 -> 4 (nums[2]=1 reaches index 3, but 0 -> 1 -> 4 also works). The last index 4 is reachable.

Input: ([3, 2, 1, 0, 4],)

Expected Output: False

Explanation: The best you can do is reach index 3 (from index 0 with jump 3). nums[3]=0 is a dead end, so index 4 is unreachable.

Input: ([0],)

Expected Output: True

Explanation: Single element array — you already start at the last index.

Input: ([2, 0, 0],)

Expected Output: True

Explanation: nums[0]=2 jumps directly over the two zeros to the last index 2.

Input: ([1, 0, 1, 0],)

Expected Output: False

Explanation: From index 0 you can only reach index 1, where nums[1]=0 traps you before the rest of the array.

Input: ([5, 0, 0, 0, 0, 0],)

Expected Output: True

Explanation: A single large first jump (range 5) covers all the trailing zeros and reaches the last index.

Input: ([0, 1],)

Expected Output: False

Explanation: nums[0]=0 means you cannot move from the start, so the last index is unreachable.

Input: ([1, 1, 1, 1],)

Expected Output: True

Explanation: Stepping one index at a time walks straight to the last index.

Hints

You do not need to track which exact path you take — only how far you can possibly reach. Maintain a single running maximum of the farthest reachable index.
Iterate left to right. If the current index ever exceeds the farthest index you can reach, you are stuck and the answer is false.
At each reachable index i, update farthest = max(farthest, i + nums[i]). As soon as farthest reaches the last index, you can stop and return true. This greedy scan is O(n) time and O(1) space — no backtracking needed.

Quick Overview

This question evaluates a candidate's understanding of array traversal and reachability in sequences of jumps, along with the ability to reason about algorithmic time and space complexity.