DSA · Greedy · #93
Jump Game II
Module 51 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given a 0-indexed integer array `nums` of length `n`. You start at index `0`. Each element `nums[i]` represents the maximum forward jump length from index `i`: from index `i` you can reach any index `j` with `i < j <= i + nums[i]`. Implement `jump(nums)` that returns the **minimum number of jumps** needed to reach the last index `n - 1`. The test cases are generated so that the last index is always reachable.
Examples
nums = [2,3,1,1,4]→2— Jump 1 step from index 0 to index 1, then 3 steps to the last index. Two jumps.nums = [2,3,0,1,4]→2— 0 -> 1 -> 4.nums = [3,2,1,0,4]→2— The first jump from index 0 (value 3) opens a window up to index 3; a second jump is then needed to cover the last index. Two jumps.
Constraints
- · 1 <= nums.length <= 10^4
- · 0 <= nums[i] <= 1000
- · It is guaranteed that you can reach nums[n - 1].
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.