70. Climbing Stairs

Solution

It’s just a Fibonacci sequence starting with 1 and 2.

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    let oneBefore = 2;
    let twoBefore = 1;
    let total = 0;
    
    for (let i = 2; i < n; i++) {
        total = oneBefore + twoBefore;
        twoBefore = oneBefore;
        oneBefore = total;
    }
    
    return total;
};

or

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let a = 1;
    let b = 1
    while (n--) {
        b += a;
        a = b - a
    }
    return a
};

Complexity

  • Time Complexity: O(N), where N is the height of the stairs, or n.
  • Space Complexity: O(1), we are not using any extra memory.

All Solutions