algoadvance

Leetcode 70. Climbing Stairs

Problem Statement

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Function Signature:

public int climbStairs(int n)

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top:
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top:
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Clarifying Questions

1. Constraints:
   • n is a positive integer (1 ≤ n ≤ 45).
2. Output:
   • Return the number of distinct ways to climb to the top.

Strategy

This problem can be approached using a dynamic programming technique similar to the Fibonacci sequence where:

• dp[i] represents the number of ways to reach the i-th step.
• To reach step i, one could have come from step i-1 or step i-2. Therefore, the relation is: [ dp[i] = dp[i-1] + dp[i-2] ]
• Base cases:
  • dp[1] = 1 (one way to climb one step)
  • dp[2] = 2 (two ways to climb to the second step, i.e., [1step + 1step] or [2 steps])

Code

Here is the Java code to solve the problem:

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

Time Complexity

• Time Complexity: The time complexity of this solution is (O(n)) because we compute the solution in a single pass through the stairs up to n.
• Space Complexity: The space complexity is also (O(n)) because we use an array of size n + 1 to store the intermediate results. However, we can optimize this to (O(1)) by using two variables to store dp[i - 1] and dp[i - 2] instead of a full array. Here is the optimized version:

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int first = 1;
        int second = 2;
        int result = 0;

        for (int i = 3; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }

        return second;
    }
}

In the optimized version, the space complexity is reduced to (O(1)) while maintaining the same (O(n)) time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?