Jump Game Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Jump Game Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the Jump Game problem changes as the input grows.

Specifically, how the number of steps to check jumps grows with the size of the input array.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function canJump(nums: number[]): boolean {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}
    

This code checks if you can jump from the start to the end of the array using the maximum reachable index at each step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each element of the array once.
• How many times: The loop runs exactly once for each element, so n times if the array length is n.

How Execution Grows With Input

As the array gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows in a straight line with input size; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide if you can jump to the end grows directly with the size of the input array.

Common Mistake

[X] Wrong: "Because we check jumps from each position, the time is much bigger than n, maybe n squared."

[OK] Correct: The code only moves forward once and updates the farthest reachable index without nested loops, so it never repeats work for the same positions.

Interview Connect

Understanding this linear time solution shows you can find efficient ways to solve problems by tracking progress smartly, a skill valued in many coding challenges.

Self-Check

"What if we changed the code to try all possible jumps from each position instead of tracking the max reach? How would the time complexity change?"