Leetcode 45: Jump Game II

1. Problem Statement (Simple Explanation):

You are given:

• A 0-indexed array nums of length n.

• You start at index 0.

Each nums[i] tells you the maximum forward jump length from index i:

• From i, you can jump to any index i + j such that:

• 0 <= j <= nums[i]

• i + j < n

You must return the minimum number of jumps needed to reach index n-1 (the last index).

You are guaranteed that this is always possible.

2. Examples:

Example 1:

Input: nums = [2,3,1,1,4]

One optimal strategy:

• From index 0 (value 2), you can reach indices 1 or 2.

• If you jump to index 1 (value 3), from there you can jump directly to index 4.

Total jumps: 2.

Output: 2

Example 2:

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

Again:

• From index 0, jump to index 1.

• From index 1, you can jump directly to index 4.

Total jumps: 2.

Output: 2

3. Intuition – Greedy "Level" / Interval Expansion:

Think of it like this:

• You are expanding layers of reachable indices, similar to BFS levels in a graph, but you can do it in one pass with greedy.

Maintain:

• jumps – number of jumps taken so far.

• currentEnd – the furthest index you can reach with jumps jumps.

• farthest – the furthest index you can reach with jumps + 1 jumps (while scanning within current range).

Idea:

Traverse from left to right (excluding last index):

• For each index i:

• Update farthest = max(farthest, i + nums[i]).

• If you reach currentEnd:

• You’ve just explored all indices reachable with the current jumps.

• You now need one more jump:

• jumps++

• currentEnd = farthest

• Once currentEnd reaches or passes the last index, you know the number of jumps.

This is analogous to:

• currentEnd is the boundary of the current “layer” of BFS.

• farthest is the maximum boundary for the next layer.

Example Walkthrough – [2,3,1,1,4]:

• n = 5

• Initialize:

• jumps = 0

• currentEnd = 0

• farthest = 0

Iterate i from 0 to n - 2 (we don't need to process last index):

• i = 0:

• farthest = max(0, 0 + nums[0]=2) = 2

• i == currentEnd (0):

• jumps = 1

• currentEnd = farthest = 2

• i = 1:

• farthest = max(2, 1 + nums[1]=3) = 4

• i = 2:

• farthest = max(4, 2 + nums[2]=1=3) = 4

• i == currentEnd (2):

• jumps = 2

• currentEnd = farthest = 4 (which is last index)

Stop; answer = 2.

Pseudo-code (Greedy):

Complexity:

Let n = len(nums):

• Time: O(n) – single pass.

• Space: O(1) – constant extra storage.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: