Maximum Number of Jumps to Reach the Last Index - Video Solutions

Problem Overview: You are given an integer array nums and a value target. Starting from index 0, you can jump to index j if |nums[j] - nums[i]| <= target and j > i. The goal is to reach the last index using the maximum number of valid jumps. If reaching the last index is impossible, return -1.

Approach 1: Dynamic Programming (O(n²) time, O(n) space)

Use dynamic programming to track the maximum jumps needed to reach each index. Create a dp array where dp[i] represents the maximum number of jumps required to reach index i. Initialize dp[0] = 0 and all other entries as negative infinity (unreachable). For each index i, iterate through all previous indices j < i. If |nums[i] - nums[j]| <= target and dp[j] is reachable, update dp[i] = max(dp[i], dp[j] + 1). This checks every valid transition and builds the best jump count incrementally. The approach runs in O(n²) time because every pair of indices may be checked, and uses O(n) space for the DP table.

Approach 2: Breadth-First Search (O(n²) time, O(n) space)

Model the array as a graph where each index represents a node and edges exist when the jump constraint is satisfied. Using breadth-first search, start from index 0 and explore all reachable indices. Each level of BFS corresponds to one additional jump. Instead of stopping at the first reach of the last index, continue exploring to track the maximum number of steps that still reach it. Maintain a queue of indices and a visited structure to avoid redundant processing. Since each node may check all future nodes for valid jumps, the worst‑case complexity remains O(n²) with O(n) extra space.

The core observation is that every jump moves forward in the array, which prevents cycles and allows either DP transitions or graph traversal. The constraint check |nums[j] - nums[i]| <= target determines whether an edge exists between two indices.

Recommended for interviews: The Dynamic Programming approach is typically expected. It directly models the problem as "maximum transitions to reach index i" and is easier to reason about during interviews. BFS demonstrates the graph interpretation and is useful when explaining alternative perspectives, but the DP solution usually communicates stronger algorithmic clarity.