Climbing Stairs

March 08, 20252 min read

Problem
You are climbing a staircase with n steps. At each step, you can climb either 1 or 2 steps. Determine the number of distinct ways to reach the top.

Description

You have to count the sequences of 1 and 2 steps that add up to n (order matters) ex: 1.Input: "n = 3" -> 3 explanation: (1 + 1 + 1) or (1 + 2) or (2 + 1)

Assumptions

The input n is a positive integer.

Approach

To solve this problem, write down the number of ways you can combine 1 and 2 steps to reach the top. For example: n= 2 => (1+1) or (2) →2 n= 3 => (1+1+1) or (2+1) or (1+2) →3 n= 4 => (1+1+1+1) or (2+1+1) or (1+2+1) or (1+1+2) or (2+2) →5 n= 5 => (1+1+1+1+1) or (2+1+1+1) or (1+2+1+1) or (1+1+2+1) or (1+1+1+2) or (1+2+2) or (2+1+2) or (2+2+1) →8

As you can see, the result for n is the sum of the results for n-1 and n-2. for n = 4 => 3 + 2 => 5 for n = 5 => 4 + 3 => 5+3 =>8

This recurrence is similar to the Fibonacci sequence, and it can be computed in two ways:

bottom-up -> while loop
recursive

Solution

//assumption is that the input is a positive integer
function climbingStairs(n) {
  if (n <= 3) {

    return n;
  }

  let i = 3
  let s = [2, 3];
  while (i < n) {
    s[1] = s[0] + s[1]
    s[0] = s[1] - s[0];
    i++;
  }

  return s[1]

}

function climbingStairs2(n, list = [2, 3], i = 3) {
  if (n <= 3) {

    return n;
  }

  if (i < n) {
    list[1] = list[0] + list[1]
    list[0] = list[1] - list[0];

    return climbingStairs2(n, list, i + 1)
  }

  return list[1]
}

Explanation

The first solution uses a while loop to build the result iteratively. It keeps the number of ways to reach the last two steps in a two-element array, s. On each pass it stores the sum of the two in s[1], and s[0] = s[1] - s[0] gets back the old s[1], so no temp variable is needed.
The recursive approach follows the same logic, but instead of looping it passes the array and i + 1 to the next call.

Conclusion

Both solutions are O(n). In this code, the loop and the recursive call both advance i from 3 while i < n. In runtimes without proper tail call optimization, each recursive call adds a stack frame, and very large inputs can overflow the stack. The iterative version avoids that stack growth and is generally more efficient and easier to read.