Day 31: Climbing Stairs : leetcode: python3

Buy me a coffee

 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?

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

Constraints:

• 1 <= n <= 45

  SOLUTION:

class Solution:

    def climbStairs(self, n: int) -> int:

        pOne, pTwo = 1, 1

        for i in range(n-1):

            temp = pOne

            pOne = pOne + pTwo

            pTwo = temp

        return pOne

Time Complexity: O(n)

Space Complexity:O(1)

How it works:

The climbStairs function takes an integer n as input and returns the number of distinct ways to climb to the top of the staircase.

The variables pOne and pTwo are initialized to 1. These variables represent the number of distinct ways to reach the current step and the previous step, respectively.

A loop is executed n-1 times because the loop starts from the second step and goes up to the nth step.

Inside the loop, the value of pOne is updated by adding pOne and pTwo, and the value of pTwo is updated to the previous value of pOne.

By doing this, we are essentially calculating the number of distinct ways to reach the current step by either taking 1 step from the previous step (pOne) or 2 steps from two steps ago (pTwo).

At the end of the loop, pOne will hold the number of distinct ways to reach the nth step.