Determine Whether the Last Array Index Is Reachable by Forward Jumps
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of non-negative integers `nums` and start at index `0`. The value `nums[i]` is the longest jump you may make from index `i`: from `i` you may move forward to any index `j` with `i < j <= i + nums[i]`, as long as `j` is a valid index.
Return `True` if some sequence of jumps reaches the last index, `len(nums) - 1`, and `False` otherwise.
### Function Signature
```python
def can_reach_last_index(nums: list[int]) -> bool:
```
### Rules
- Jumps only move forward, and from index `i` you may choose any jump length from `1` up to `nums[i]`. A jump may not land beyond the last index, but any shorter jump is still allowed.
- A value of `0` means no jump can be made from that index.
- If `nums` has a single element, you are already at the last index, so the answer is `True`.
### Constraints
- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^5`
### Examples
**Example 1**
- Input: `nums = [1, 2, 0, 3, 0]`
- Output: `True`
- Explanation: Jump from index `0` to index `1`, then a jump of length 2 from index `1` to index `3`, then from index `3` to the last index, `4`.
**Example 2**
- Input: `nums = [3, 1, 1, 0, 2]`
- Output: `False`
- Explanation: Indices `1`, `2` and `3` are reachable, but every route ends at index `3`, whose value is `0`. Index `4` is never reached.
**Example 3**
- Input: `nums = [0]`
- Output: `True`
- Explanation: The start is already the last index.
Overview: Decide whether the last index of an array can be reached from the first when each value gives the longest forward jump allowed from that position. Tests reachability reasoning, handling zero values that can block progress, and designing a linear-time solution for large inputs.
Read the full Google Software Engineer interview experience this question came from
You are given a list of non-negative integers `nums` and you start at index `0`. The value `nums[i]` is the longest jump you may make from index `i`: from index `i` you may move forward to any index `j` with `i < j <= i + nums[i]`, as long as `j` is a valid index.
Return `True` if some sequence of jumps reaches the last index, `len(nums) - 1`, and `False` otherwise.
Implement `can_reach_last_index(nums)`.
**Rules**
- Jumps only move forward. From index `i` you may choose any jump length from `1` up to `nums[i]`. A jump may not land beyond the last index, but any shorter jump is still allowed.
- A value of `0` means no jump can be made from that index.
- If `nums` has a single element, you are already at the last index, so the answer is `True`.
- The answer is a single boolean, so every input has exactly one correct output.
**Constraints**
- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^5`
- The farthest reach `i + nums[i]` is below `2 * 10^5`, so it fits in a 32-bit signed integer.
**Example 1**
- Input: `nums = [1, 2, 0, 3, 0]`
- Output: `True`
- Explanation: Jump from index `0` to index `1`, then a jump of length 2 from index `1` to index `3`, then from index `3` to the last index, `4`.
**Example 2**
- Input: `nums = [3, 1, 1, 0, 2]`
- Output: `False`
- Explanation: Indices `1`, `2` and `3` are reachable, but every route ends at index `3`, whose value is `0`. Index `4` is never reached.
**Example 3**
- Input: `nums = [0]`
- Output: `True`
- Explanation: The start is already the last index.
Constraints
- 1 <= len(nums) <= 10^5
- 0 <= nums[i] <= 10^5
Examples
Input: ([1, 2, 0, 3, 0],)
Expected Output: True
Explanation: Source example 1: 0 -> 1 -> 3 -> 4.
Input: ([3, 1, 1, 0, 2],)
Expected Output: False
Explanation: Source example 2: every route ends on the zero at index 3.
Hints
- You never need to know which exact path you took, only which indices are reachable at all.
- If index i is reachable, is every index before i also reachable? What single number summarizes the reachable set?
- Scan left to right and stop as soon as you reach an index that nothing before it can reach.
Community answers
Answer by mojahidislam221
int potential = nums.length - 1;
for(int i=nums.length-2;i>=0;i--){
if(nums[i] + i>=potential){
potential = i;
}
}
return potential == 0;
}