11. Minimum Number of Jumps to Reach End of Array

Given an array where arr[i] is the maximum number of steps you can jump forward from index i, find the minimum number of jumps needed to reach the last index starting from index 0. If it's impossible, print -1.

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers, where arr[i] is the maximum forward jump length from index i. Output: Print the minimum number of jumps to reach the last index, or -1 if it is unreachable.

1 <= n <= 10^5, 0 <= arr[i] <= 1000

If arr[0] is 0 and the array has more than one element, the very first index can't move at all - correctly reporting -1 for this edge case is an easy thing to forget.

Starting at the first index of an array, where each value tells you the FARTHEST you're allowed to jump forward from there, find the fewest jumps needed to reach the last index. Brute force: Try every possible sequence of jumps recursively (at each index, try every allowed jump length) and find the shortest path to the end - this branches exponentially, far too slow for large arrays. Optimised: A greedy approach works because you never need to explore every combination - at each point, you only need to track the FARTHEST index reachable with the jumps used so far, and greedily commit to a new jump only when forced to (when you've exhausted your current range) - this guarantees the minimum jump count in a single linear pass.

From each index, recursively try every possible jump length from 1 up to arr[i], and recursively compute the minimum jumps needed from the resulting index, taking the best result across all choices plus one. This directly explores every possible sequence of jumps to the end, which is correct but branches so heavily that the number of paths explored grows exponentially with the array size. Time: O(2^n) Space: O(n)

Think of the problem as a breadth-first search over 'jump levels': maintain the farthest index reachable using the jumps taken so far (currentEnd) and the farthest index reachable if one more jump is used from anywhere within the current range (farthest). Scan left to right; whenever the current index reaches currentEnd, one more jump is forced, so increment the jump count and set currentEnd to farthest. Because this only ever needs a single forward pass while tracking two running maximums, it finds the minimum number of jumps in linear time with constant extra space, which is optimal since every index must be examined at least once. Time: O(n) Space: O(1)

Build a dp array where dp[i] is the minimum number of jumps needed to reach index i from index 0, with dp[0] = 0. For each index i from 1 to n-1, look back at every earlier index j where j + arr[j] >= i (meaning a jump from j can reach i), and set dp[i] to one plus the minimum dp[j] among those. This reuses previously solved subproblems instead of re-exploring every path from scratch, collapsing the exponential brute force into a polynomial number of states, though checking all earlier j for every i still costs quadratic time overall. Time: O(n^2) Space: O(n)

1. Track the farthest index reachable using the jumps taken SO FAR, and the farthest index reachable using ONE MORE jump from anywhere within the current range. 2. Walk forward index by index, updating the 'farthest with one more jump' as you go. 3. The moment you reach the boundary of what your CURRENT jump count can cover, you're forced to take another jump - increment the jump count and extend your current boundary to the farthest reachable point found so far. 4. Stop once your reachable boundary covers the last index.

Time: O(n) - one single pass through the array, tracking two running boundaries. Space: O(1) - just a few tracking variables (current boundary, farthest reachable, jump count).

n = 1 (already at the last index, 0 jumps needed); arr[0] = 0 with n > 1 (the end is unreachable, print -1); and n = 10^5 (largest, confirming the greedy range-extension approach is O(n)).

Be ready to explain why greedy (always looking as far ahead as possible) is provably optimal here, unlike some jump-game variants - a common interview follow-up is proving this greedy choice never leads to a worse outcome than exploring alternatives.