Climbing Stairs Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of climbingStairs(4) with simple recursion

What is the output of the following TypeScript function call: climbingStairs(4)?

DSA Typescript

function climbingStairs(n: number): number {
  if (n <= 2) return n;
  return climbingStairs(n - 1) + climbingStairs(n - 2);
}

console.log(climbingStairs(4));

A 7

B 6

C 4

D 5

💡 Hint

Think about how many ways to climb 3 steps and 2 steps add up for 4 steps.

The function uses recursion where climbingStairs(n) = climbingStairs(n-1) + climbingStairs(n-2). For n=4, it calculates 3 + 2 = 5.

❓ Predict Output

intermediate

Output of climbingStairs(5) with memoization

What is the output of the following TypeScript code when calling climbingStairs(5)?

DSA Typescript

function climbingStairs(n: number, memo: Record<number, number> = {}): number {
  if (n <= 2) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = climbingStairs(n - 1, memo) + climbingStairs(n - 2, memo);
  return memo[n];
}

console.log(climbingStairs(5));

A 8

B 7

C 5

D 10

💡 Hint

Use the relation climbingStairs(n) = climbingStairs(n-1) + climbingStairs(n-2) with memoization.

climbingStairs(5) = climbingStairs(4) + climbingStairs(3) = 5 + 3 = 8. But memoization stores results to avoid repeated calls.

🔧 Debug

advanced

Identify the error in climbingStairs iterative solution

What error will the following TypeScript code produce when calling climbingStairs(3)?

DSA Typescript

function climbingStairs(n: number): number {
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

console.log(climbingStairs(3));

A Returns 2

B Runtime error: undefined variable

C Returns 3

D Returns 5

💡 Hint

Check initial values and loop start index carefully.

The function returns 3 for climbingStairs(3) because it correctly sums ways for steps 1 and 2 and iterates once for step 3.

🧠 Conceptual

advanced

Number of ways to climb 0 steps

According to the climbing stairs problem, how many ways are there to climb 0 steps?

A 2 ways

B 1 way (do nothing)

C Undefined

D 0 ways

💡 Hint

Think about the base case for no steps.

There is exactly 1 way to climb 0 steps: by not climbing at all. This is the base case in many solutions.

🚀 Application

expert

Minimum number of jumps to reach the top

Given an array where each element represents the maximum jump length from that position, what is the minimum number of jumps to reach the last index? For example, for [2,3,1,1,4], what is the minimum jumps needed?

A 2

B 3

C 4

D 1

💡 Hint

Try to jump to the farthest reachable index at each step.

From index 0 jump 1 step to index 1, then jump 3 steps to the last index. Total jumps = 2.

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