Problem

Given an integer list where each number represents the number of hops you can make, determine whether you can reach to the last index starting at index 0.

Examples

Example 1

1
2
3

Input: [2, 0, 1, 0]
Output: True
Explanation: Starting from index 0, you can hop to index 2, then hop to the last index.

Example 2

1
2
3

Input: [1, 1, 0, 1]
Output: False
Explanation: Starting from index 0, you can only reach index 2. From there, you cannot move further.

Solution

Method 1 - Greedy

Here is the approach:

  1. Initialize:
    • Set the current position at the start.
    • Iterate through the list while validating that hops do not lead to indices that block further progress.
  2. Logic:
    • If at any point you reach a zero before arriving at the last index and there’s no way to bypass the zero, return False.
    • Only if traversal leads you to the last index return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public boolean canReachLastIndex(int[] hops) {
        int length = hops.length;
        int currPos = 0, lastIndex = length - 1;
        
        while (currPos < length) {
            if (currPos == lastIndex) {
                return true;
            } else if (hops[currPos] == 0) {
                return false;
            }
            currPos += hops[currPos];
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // Example usage
        System.out.println(solution.canReachLastIndex(new int[] {2, 0, 1, 0})); // Output: true
        System.out.println(solution.canReachLastIndex(new int[] {1, 1, 0, 1})); // Output: false
        System.out.println(solution.canReachLastIndex(new int[] {3, 3, 0, 0, 1})); // Output: false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def can_reach_last_index(hops: List[int]) -> bool:
    length = len(hops)
    curr_position, last_index = 0, length - 1
    while curr_position < length:
        if curr_position == last_index:
            return True
        elif hops[curr_position] == 0:
            return False
        curr_position += hops[curr_position]
    return False

# Example usage
if __name__ == "__main__":
    # Test cases
    print(can_reach_last_index([2, 0, 1, 0]))  # Output: True
    print(can_reach_last_index([1, 1, 0, 1]))  # Output: False
    print(can_reach_last_index([3, 3, 0, 0, 1]))  # Output: False

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the list.
  • 🧺 Space complexity: O(1) as the operations are performed in-place without extra space.