Jump to the End

Determine if you can reach the last index of an array given jump lengths at each position. This tests dynamic programming and greedy approaches common in technical interviews.

arraygreedydynamic programmingalgorithm

Problem Statement

You are given a non-empty array of non-negative integers called 'hops'. Each element in 'hops' represents the maximum number of indices you can advance from that position. Starting from the first index (index 0), determine if it is possible to reach the last index of the array.

Example 1

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

Output: True

Starting at index 0, you can jump a maximum of 4 indices, landing you at the last index. Therefore, it is possible to reach the end.

Example 2

Input: [3, 0, 1, 0, 0]

Output: False

Starting at index 0, you can jump a maximum of 3 indices, landing you at index 3. From index 3, you cannot proceed further because the value is 0. Similarly, from index 1, you cannot proceed further. Therefore, it is impossible to reach the last index.

Constraints

-The input array 'hops' will have at least one element.
-All elements in the 'hops' array will be non-negative integers.
-The array length will not exceed 10,000.
-Each element in the array will be less than 1000.

Brute Force Approach

Imagine you are exploring a maze, and at each intersection, you try every possible path until you either find the exit or exhaust all options. In this problem, the brute-force approach would involve recursively exploring every possible jump combination from each index. This would have exponential time complexity because of overlapping subproblems and would use minimal extra space.

TimeO(2^n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem