LeetCode #70: Climbing Stairs

LeetCode Solutions

https://leetcode.com/problems/climbing-stairs/

To solve this problem, we need to keep track of the number of ways we can climb to reach the current stair. We can do this by keeping track of the number of ways to reach the previous two stairs. We can then use this information to calculate the number of ways to reach the current stair. This is because we can either take a single step from the previous stair or take two steps from the stair two steps back.

Here are the steps to solve this problem:

  1. If the number of stairs is 1, return 1.
  2. Initialize two variables to store the number of ways to reach the first two stairs.
  3. Loop through the remaining stairs (starting from the third stair).
  4. Calculate the number of ways to reach the current stair by adding the number of ways to reach the previous two stairs.
  5. Update the variables storing the number of ways to reach the previous two stairs.
  6. Return the number of ways to reach the top stair.

Here’s the solution in Python:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        one_back = 2
        two_back = 1
        for i in range(2, n):
            curr = one_back + two_back
            two_back = one_back
            one_back = curr
        return one_back

Time Complexity

We need to loop through n stairs, so the time complexity of this algorithm is O(n).

Space Complexity

We only need to store the number of ways to reach the previous two stairs, so the space complexity of this algorithm is O(1).