Coding Interview Questions | Climbing Stairs

December 28th, 2023

Climbing Stairs Problem Introduction:

This summary will talk about my solution to the climbing stairs problem as seen on leetcode here.

Climbing Stairs Problem Solution:

function climbStairs(n: number): number {
  // [0] {0}, n = 1, answer = 1
  // [0, 1] {[0, 1], [1]}, n = 2, answer = 2
  // [0, 1, 2] {[0, 1, 2], [1, 2], [0, 2]}, n = 3, answer = 3
  // [0, 1, 2, 3] {[0, 1, 2, 3], [1, 2, 3], [1, 3], [0, 2, 3], [0, 1, 3]} n = 4, answer = 5

  const nCountMap = new Map<number, number>();
  nCountMap.set(1, 1);
  nCountMap.set(2, 2);

  for (let step = 3; step <= n; step++) {
    nCountMap.set(step, nCountMap.get(step - 1)! + nCountMap.get(step - 2)!);
  }

  return nCountMap.get(n)!;
}

Climbing Stairs Problem Summary:

• Dynamic Programming Approach: The solution above employs a dynamic programming strategy to calculate the distinct ways of climbing stairs.
• Memoization with Map: Intermediate results are stored in a Map, serving as a memoization mechanism to avoid redundant computations.
• Base Cases Initialization: The algorithm initializes base cases for the first two steps, establishing the foundation for subsequent calculations.
• Iterative Computation: A loop iterates from step 3 to the target step n, dynamically updating the memoization map based on the results of the previous two steps.
• Complexities: Overall, the time complexity and space complexity of the solution is O(n).

Why this algorithm works:

For steps beyond the initial base cases (n > 2), the number of ways to reach the current step (n) is the sum of the ways to reach the two previous steps (n-1) and (n-2).

Mathematically, it can be expressed as: ways(n) = ways(n-1) + ways(n-2)

This is because you can reach the current step either by taking a single step from the previous step (n-1) or by taking two steps from the step before that (n-2).