Skip to content

The Jumping Game

Level: L3 Topics: Dynamic Programming, Greedy, Arrays

Problem Statement

You are given an array of positive integers. Starting at index 0, at each position you have two choices:

  1. Skip: Move to the next index (i + 1) and score 0 points.
  2. Take: Score the value at the current index, then jump forward by that value (move to index i + arr[i]).

If a jump or skip takes you beyond the end of the array, the game ends. Find the maximum total points you can earn.

Background & Constraints

  • The array contains only positive integers (all values >= 1).
  • You always start at index 0.
  • "Skip" moves you exactly one position forward.
  • "Take" at index i gives you arr[i] points and moves you to index i + arr[i].
  • The game ends when you move past the last index.
  • Array length can be up to 10^4.

Examples

Example 1:

Array: [2, 3, 1, 4, 2]

Option A: Take 2 (jump to index 2), Take 1 (jump to index 3), Take 4 (jump to index 7, game over)
Points: 2 + 1 + 4 = 7

Option B: Skip (index 1), Take 3 (jump to index 4), Take 2 (jump to index 6, game over)
Points: 3 + 2 = 5

Option C: Take 2 (jump to index 2), Skip (index 3), Take 4 (jump to index 7, game over)
Points: 2 + 4 = 6

Maximum points: 7

Example 2:

Array: [1, 1, 1, 1]

Taking every value: Take 1 (jump to 1), Take 1 (jump to 2), Take 1 (jump to 3), Take 1 (jump to 4, end)
Points: 4

This is optimal since skipping never helps when values are all 1.
Maximum points: 4

Hints & Common Pitfalls

  • DP formulation: Let dp[i] = maximum points achievable starting from index i. Work backwards from the end of the array.
  • Recurrence: dp[i] = max(dp[i+1], arr[i] + dp[i + arr[i]]) where dp[i+1] represents skipping and arr[i] + dp[i + arr[i]] represents taking. Handle out-of-bounds indices by treating them as 0.
  • Base case: For indices beyond the array, dp = 0.
  • Common mistake: Using greedy by always taking the larger value. This doesn't work because taking a large value might skip over even larger values ahead.
  • The O(n) DP solution (one pass from right to left) is optimal.

Follow-Up Questions

  1. Return the actual sequence of moves (which indices you take) that achieves the maximum score.
  2. What if the array can contain zeros? (Taking a zero means you stay at the same index — infinite loop risk.)
  3. What if the array can contain negative values? You might choose to take a negative to reach a more valuable position.
  4. What is the time and space complexity of your solution? Can you optimize the space?
  5. What if instead of jumping forward by arr[i], you can jump to any index in the range [i+1, i+arr[i]]?