Jump Game II

MediumGreedygreedy bfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a 0-indexed integer array nums of length n. You begin standing at index 0, and your goal is to reach the last index n - 1. The value nums[i] tells you the **maximum** distance you may jump forward from index i. In other words, if you are standing at index i, you can jump to any index j such that i < j <= i + nums[i] (and j stays within the array). Return the **minimum number of jumps** required to reach the last index. The input is guaranteed to be constructed so that the last index is always reachable from index 0.

Examples

Input: nums = [2,3,1,1,4]
Output: 2
Jump 1 step from index 0 to index 1 (since nums[0] = 2 lets you reach index 1 or 2), then jump 3 steps from index 1 to the last index. That is 2 jumps total.
Input: nums = [2,3,0,1,4]
Output: 2
Jump from index 0 to index 1, then from index 1 (which can reach up to index 4) directly to the last index.
Input: nums = [0]
Output: 0
You already start at the last index, so no jumps are needed.

Constraints

  • `1 <= nums.length <= 10^4`
  • `0 <= nums[i] <= 1000`
  • It is guaranteed that you can reach `nums[nums.length - 1]`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.