Skip to main content

49. Jump Game

mediumAsked at Datadog

Determine if you can reach the last index given an array of max jump lengths. Datadog asks this for the greedy max-reach pattern — same shape as a streaming reachability check over a partially-observed graph.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite greedy question.
  • Blind (2025-12)— Recurring at Datadog.

Problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

Examples

Example 1

Input
nums = [2,3,1,1,4]
Output
true

Example 2

Input
nums = [3,2,1,0,4]
Output
false

Approaches

1. DP from each cell

dp[i] = can reach end from i. Fill right-to-left.

Time
O(n^2)
Space
O(n)
function canJump(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(false);
  dp[n - 1] = true;
  for (let i = n - 2; i >= 0; i--) {
    for (let j = 1; j <= nums[i] && i + j < n; j++) {
      if (dp[i + j]) { dp[i] = true; break; }
    }
  }
  return dp[0];
}

Tradeoff: Quadratic. Datadog will push for O(n).

2. Greedy max-reach (optimal)

Walk left to right; maintain max-reach. If max-reach < i, you can't get here. If max-reach >= n-1, return true.

Time
O(n)
Space
O(1)
function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return true;
}

Tradeoff: Single pass, O(1) state. Datadog-canonical: the running-max pattern is the same streaming aggregate they use for reachability.

Datadog-specific tips

Datadog grades on whether you recognize this as a greedy problem, not DP. The key insight — at every step, only the MAX-reach-so-far matters, not which path got us there — is what they want to hear before you code.

Common mistakes

  • Iterating right-to-left like DP would — works but is unnecessary.
  • Forgetting the i > maxReach early-exit — wastes work after a dead end.
  • Using <= instead of < in the dead-end check — off by one.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Jump Game II (LC 45) — minimum number of jumps.
  • Jump Game III (LC 1306) — bidirectional jumps.
  • Datadog-style: streaming reachability over a partially-observed graph.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why greedy works?

We only care whether SOME path reaches the end. At each index, the optimal future depends only on maxReach so far — not on which earlier index achieved it.

What if nums[i] is 0?

You can't jump from i. maxReach doesn't grow at i. If maxReach is still > i, you might land beyond i; otherwise you're stuck.

Practice these live with InterviewChamp.AI

Drill Jump Game and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →