/45. Jump Game II

45. Jump Game II

Medium
Arrays42.6% acceptance

Given an integer array jump_limits of length n, where jump_limits[i] represents the maximum number of indices you can move forward from index i, determine the minimum number of jumps required to reach the last index (n - 1) starting from index 0. It is guaranteed that the last index is reachable from the starting index.

Example 1

Input: [1, 2, 1, 1, 1]

Output: 3

Explanation: Jump from 0->1, 1->3, 3->4.

Example 2

Input: [5, 1, 1, 1, 1, 1]

Output: 1

Explanation: Jump directly from 0 to 5.

Constraints

  • 1 <= len(jump_limits) <= 10_000
  • 0 <= jump_limits[i] <= 1000 for all valid i
  • It is guaranteed that the last index is reachable from the first index
Python (current runtime)

Case 1

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

Expected: 2

Case 2

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

Expected: 2

Case 3

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

Expected: 2

Case 4

Input: [1, 1, 1, 1, 1, 1]

Expected: 5

Case 5

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

Expected: 2