Climbing Stairs Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Climbing Stairs Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the climbing stairs problem changes as the number of stairs grows.

Specifically, how many steps does the program take to find the total ways to climb?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let first = 1, second = 2;
  for (let i = 3; i <= n; i++) {
    const third = first + second;
    first = second;
    second = third;
  }
  return second;
}
    

This code calculates how many distinct ways there are to climb n stairs, taking 1 or 2 steps at a time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs from 3 up to n.
• How many times: It runs (n - 2) times, once for each stair from 3 to n.

How Execution Grows With Input

Each new stair requires one addition and two variable updates inside the loop.

Input Size (n)	Approx. Operations
10	8 additions and updates
100	98 additions and updates
1000	998 additions and updates

Pattern observation: The number of operations grows roughly in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the number of ways grows directly in proportion to the number of stairs.

Common Mistake

[X] Wrong: "Because the problem involves Fibonacci numbers, it must take exponential time."

[OK] Correct: This code uses a simple loop and stores only two previous results, so it runs in linear time, not exponential.

Interview Connect

Understanding this problem helps you practice turning recursive ideas into efficient loops, a skill often needed in interviews.

Self-Check

"What if we changed the problem to allow steps of 1, 2, or 3 at a time? How would the time complexity change?"

Practice

1. What does the Climbing Stairs problem ask you to find?
Given n stairs, how many distinct ways can you climb to the top if you can take 1 or 2 steps at a time?

easy

A. The maximum number of steps you can take at once

B. The minimum number of steps to reach the top

C. The number of stairs you skip

D. The total number of distinct ways to reach the top

Solution

1. Step 1: Understand the problem statement

   The problem asks for the count of different ways to climb n stairs taking 1 or 2 steps at a time.

2. Step 2: Identify what is being asked

   We want the total number of distinct sequences of 1-step and 2-step moves that sum to n.

3. Final Answer:

   The total number of distinct ways to reach the top -> Option D

4. Quick Check:

   Count ways = total distinct sequences [OK]

Hint: Count sequences of 1 or 2 steps to reach n [OK]

Common Mistakes:

• Confusing number of ways with minimum steps
• Thinking about maximum steps allowed
• Counting skipped stairs instead of ways

2. Which of the following TypeScript function signatures correctly represents a function to solve the Climbing Stairs problem?

easy

A. function climbStairs(n: number): number

B. function climbStairs(n: string): string

C. function climbStairs(): void

D. function climbStairs(n: number): void

Solution

1. Step 1: Identify input and output types

   The input is the number of stairs (number), output is the count of ways (number).

2. Step 2: Match function signature

   Only the signature with input number and output number matches the problem requirements.

3. Final Answer:

   function climbStairs(n: number): number -> Option A

4. Quick Check:

   Input and output types match problem [OK]

Hint: Input and output both must be numbers [OK]

Common Mistakes:

• Using string type for number input
• Function returning void instead of number
• No input parameter in function

3. What is the output of the following TypeScript code?

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    let temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}
console.log(climbStairs(4));

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace initial values and loop

   For n=4, start with a=1, b=2. Loop i=3 to 4: - i=3: temp=1+2=3, a=2, b=3 - i=4: temp=2+3=5, a=3, b=5

2. Step 2: Return final value

   Return b=5 as the number of ways to climb 4 stairs.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Ways for 4 stairs = 5 [OK]

Hint: Use Fibonacci-like addition for steps count [OK]

Common Mistakes:

• Returning a instead of b
• Off-by-one error in loop
• Incorrect initial values for a and b

4. Identify the error in this TypeScript code for climbing stairs:

function climbStairs(n: number): number {
  if (n == 1) return 1;
  let a = 1, b = 2;
  for (let i = 2; i <= n; i++) {
    let temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

medium

A. Initial values of a and b are incorrect

B. Return statement should return a instead of b

C. Loop starts at wrong index causing off-by-one error

D. Missing base case for n == 2

Solution

1. Step 1: Analyze loop start and base cases

   Loop starts at i=2 but initial values assume i=3 start. This causes extra iteration and wrong count.

2. Step 2: Correct loop start

   Loop should start at i=3 to align with initial values a=1, b=2 and base case for n=2.

3. Final Answer:

   Loop starts at wrong index causing off-by-one error -> Option C

4. Quick Check:

   Loop index must match initial conditions [OK]

Hint: Check loop start matches base cases [OK]

Common Mistakes:

• Starting loop at 2 instead of 3
• Ignoring base case for n=2
• Swapping a and b updates

5. You want to find the number of ways to climb 10 stairs but now you can take 1, 2, or 3 steps at a time. Which modification to the climbing stairs logic is correct?

hard

A. Use dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

B. Use dp[i] = dp[i-1] * dp[i-2] * dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

C. Use dp[i] = dp[i-1] + dp[i-2] only with base dp[0]=1, dp[1]=1

D. Use dp[i] = dp[i-1] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

Solution

1. Step 1: Understand the new step options

   Now steps can be 1, 2, or 3 at a time, so ways to reach i depend on previous 3 states.

2. Step 2: Formulate recurrence relation

   Number of ways to reach step i = sum of ways to reach i-1, i-2, and i-3.

3. Step 3: Set base cases

   dp[0]=1 (one way to stand still), dp[1]=1, dp[2]=2 (1+1 or 2 steps).

4. Final Answer:

   Use dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2 -> Option A

5. Quick Check:

   Sum previous 3 states for new step sizes [OK]

Hint: Sum ways from last 3 steps for 1,2,3 moves [OK]

Common Mistakes:

• Multiplying previous states instead of adding
• Ignoring the 3-step option
• Wrong base cases for dp array