Python Programming Challenge 22: Climbing Stairs (Leetcode 70)

For today’s post, we’ll discuss the Climbing Stairs problem from Leetcode.

The Climbing Stairs Problem

The Climbing Stairs problem requires us to write a function called climbStairs() that accepts one input n, where n represents the number of steps of a stairs. The function needs to return the number of unique ways to reach the top of the stairs, given that at any one time, you can either climb 1 or 2 steps.

For instance, if the stairs has 2 steps, there are 2 ways to reach the top:

1 step + 1 step, or
2 steps

If the stairs has 4 steps, there are 5 ways to reach the top:

1 step + 1 step + 1 step + 1 step
1 step + 1 step + 2 steps
1 step + 2 steps + 1 step
2 steps + 1 step + 1 step
2 steps + 2 steps

Suggested Approach

The easiest way to solve the Climbing Stairs Leetcode problem is to use an approach similar to the first approach we used for the Unique Paths problem previously.

First, we need to recognize that as the Climbing Stairs problem only allows us to climb one or two steps, to reach any step on the stairs, we can either climb one step from the previous step, or two steps from the step below the previous step.

For instance, to reach the green step (which is the 4^th step) in the diagram below, we can either climb one step from the red step (the 3^rd step) or two steps from the blue one (the 2^nd step).

As there are 3 ways to reach the 3^rd step (1 + 1 + 1, 1 + 2, or 2 + 1) and 2 ways to reach the 2^nd step (1+1 or 2), we conclude that there are 3 + 2 = 5 ways to reach the 4^th step.

3 of the ways pass through the 3^rd step:
1 + 1 + 1 + 1
1 + 2 + 1
2 + 1 + 1

and 2 pass through the 2^nd step:
1 + 1 + 2
2 + 2

Based on this observation, in general, we can conclude that the number of ways to reach Step i is given by the formula

Number of ways to reach Step i = Number of ways to reach Step (i-1) + Number of ways to reach Step (i-2).

Based on the description above, try working on the challenge yourself.

Suggested Solution

Here’s the suggested solution for the Climbing Stairs Leetcode problem in Python:

def climbStairs(n):
        
    if n == 1 or n == 2:
        return n
    
    prevPrev = 1
    prev = 2
    current = 0
    
    for step in range(3, n+1):
        # Calculate Number of Ways to Reach Current Step
        current = prevPrev + prev
        # Update Pointers for Next Step
        prevPrev = prev
        prev = current

    return current

Here, we first define a function called climbStairs() with one parameter n.

Inside the function, we check if n equals 1 or 2. As the number of steps to reach the top of a stairs with 1 or 2 steps is 1 and 2 respectively, we return n if n equals 1 or 2.

Declare and initialize prevPrev, prev and current

Next, we declare and initialize 3 pointers, prevPrev, prev and current.

For any Step i (where i is greater than 2),

prevPrev stores the number of ways to reach Step (i-2),
prev stores the number of ways to reach Step (i-1), and
current stores the number of ways to reach Step i.

We first initialize prevPrev to 1 and prev to 2, which represent the number of ways to reach the first and second steps respectively.

We also initialize current to 0.

Updating Values of current, prev and prevPrev

Next, we use a for loop (lines 10 to 15) to calculate and update the values of current, prev and prevPrev, starting from the third step (i.e. starting from step equals 3).

Inside the for loop, we first calculate and update the value of current by assigning the sum of prevPrev and prev to it (line 12).

Next, we update the value of prevPrev by assigning the value of prev to it (line 14). We also update the value of prev by assigning the value of current to it (line 15).

Example when step equals 3

For instance, when step equals 3 (the first iteration), when we first enter the for loop, prevPrev stores the number of ways to reach Step 1, and prev stores the number of ways to reach Step 2.

We update the value of current to prevPrev + prev = 1 + 2 = 3 on line 12. This represents the number of ways to reach Step 3.

Next, we update the values of prevPrev and prev on lines 14 and 15. After updating, prevPrev stores the number of ways to reach Step 2, while prev stores the number of ways to reach Step 3. This prepares the pointers to be used for the next step (i.e. for Step 4).

We keep calculating and updating the values of current, prevPrev and prev until step equals n.

When that happens, current stores the number of ways to reach Step n.

The for loop ends and we return the value of current on line 17.

With that, the function is complete.

The graphical illustration below shows an example of how the suggested solution works when n equals 6.

Python Programming Challenge 22: Climbing Stairs