Min Number Of Jumps

Tags

Min Number Of Jumps

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given a non-empty array of positive integers where each element represents the maximum jump length from that position, find the minimum number of jumps needed to reach the last index starting from the first index. It is guaranteed that the last index is always reachable.

Intuition

The greedy approach works optimally here. At each step, we track the farthest position reachable from the current "level" of jumps. When we reach the boundary of the current level, we must take another jump, and the new boundary becomes the farthest position we have seen so far. This is similar to a BFS level-order traversal where each "level" represents one jump.

Approach

  1. If the array has 0 or 1 elements, return 0.
  2. Initialize: jumps = 0, currentEnd = 0, farthest = 0.
  3. Iterate through the array (up to the second-to-last index): a. Update farthest = max(farthest, i + array[i]). b. If i == currentEnd (we have reached the boundary of the current jump):
    • Increment jumps.
    • Set currentEnd = farthest.
    • If currentEnd >= lastIndex, break early.
  4. Return jumps.

Pseudocode

function minNumberOfJumps(array):
    if length(array) <= 1:
        return 0

    jumps = 0
    currentEnd = 0
    farthest = 0

    for i from 0 to length(array) - 2:
        farthest = max(farthest, i + array[i])
        if i == currentEnd:
            jumps += 1
            currentEnd = farthest
            if currentEnd >= length(array) - 1:
                break

    return jumps

Time & Space Complexity

  • Time: O(n), where n is the length of the array. A single pass through the array.
  • Space: O(1). Only a constant number of variables.

Key Insights

  • The greedy approach works because we are guaranteed to reach the end, and extending our reach as far as possible at each step minimizes the number of jumps.
  • This is equivalent to BFS on an implicit graph where each index has edges to all indices within its jump range.
  • A DP approach exists with O(n^2) time where dp[i] = min jumps to reach index i, but the greedy approach is superior.
  • We only iterate up to the second-to-last index because we do not need to jump from the last index.

Edge Cases

  • Array of length 1: already at the destination, return 0.
  • Array of length 2: always 1 jump (since all values are positive).
  • First element is large enough to reach the end directly: return 1.
  • All elements are 1: need exactly n-1 jumps.
  • Very large values in the array: farthest may exceed the array bounds; the early break handles this.

Linked mentions