Min Cost Climbing Stairs – Solution & Complexity

Q: What is the time and space complexity of Min Cost Climbing Stairs?

The optimal Min Cost Climbing Stairs solution runs in `O(n)` time and `O(1)` space. Roll two variables holding the cheapest cost to reach the previous two stairs and take the minimum incoming move at each step.

Q: What is the most efficient way to solve Min Cost Climbing Stairs?

Roll two variables holding the cheapest cost to reach the previous two stairs and take the minimum incoming move at each step. This gives `O(n)` time complexity, and is a classic dynamic programming and arrays problem.

Q: How do you solve Min Cost Climbing Stairs in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Min Cost Climbing Stairs solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Min Cost Climbing Stairs an easy or hard interview question?

Min Cost Climbing Stairs is generally rated **Easy**. It tests dynamic programming and arrays, which are common coding-interview patterns.

Solution Walkthrough

Step 1: Frame the recurrence
- Let best[i] be the cheapest toll paid to arrive at stair i.
- Arriving at the top means arriving at index n, one past the last stair.
- You reach stair i from either stair i-1 or stair i-2, paying that stair's toll when you leave it.

Step 2: Tabulate over a DP array

best[0] = best[1] = 0 because you may start on either stair for free.
For every later index, take the cheaper of the two incoming moves and add the toll you paid to make that move.
The answer is best[n].

def min_cost_climbing_stairs(cost: list[int]) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    return dp[n]

Step 3: Collapse to two rolling variables
- The recurrence only ever looks back two positions, so a full array is unnecessary.
- Track downOne (cost to reach the previous stair) and downTwo (the stair before that) and slide them forward.

Step 4: Optimal O(1)-space scan

Iterate from index 2 through n, computing each new arrival cost from the two rolling variables, then shift them.
After the loop, downOne holds the cost to reach the top.

def min_cost_climbing_stairs(cost: list[int]) -> int:
    down_two, down_one = 0, 0
    for i in range(2, len(cost) + 1):
        step = min(down_one + cost[i - 1], down_two + cost[i - 2])
        down_two, down_one = down_one, step
    return down_one

Step 5: Dry run
Trace cost = [10,15,20].

i downTwo downOne new step
2 0 0 min(0+15, 0+10) = 10
3 0 10 min(10+20, 0+15) = 15

The loop ends with downOne = 15, matching the expected answer.
Step 6: Common mistakes and follow-ups
- Returning dp[n-1] instead of dp[n], which stops one stair short of the top.
- Adding cost[i] when arriving instead of cost[i-1]/cost[i-2] for the stair you leave.
- Forgetting that both stair 0 and stair 1 are free starting points.
- Follow-up: how would the recurrence change if you could also climb three stairs at a time?
Step 7: Edge cases to test mentally
- The minimum length is 2; the answer is then min(cost[0], cost[1]).
- All-zero tolls cost 0.
- Alternating free and expensive stairs should always land on the free ones.

i	downTwo	downOne	new step
2	0	0	min(0+15, 0+10) = 10
3	0	10	min(10+20, 0+15) = 15

Step 8: Final full solution and complexity

A single left-to-right scan keeps two rolling subresults. Time is O(n) and extra space is O(1).

def min_cost_climbing_stairs(cost: list[int]) -> int:
    down_two, down_one = 0, 0
    for i in range(2, len(cost) + 1):
        step = min(down_one + cost[i - 1], down_two + cost[i - 2])
        down_two, down_one = down_one, step
    return down_one

Min Cost Climbing Stairs – Solution & Complexity

Solution Walkthrough

Step 1: Frame the recurrence

Step 2: Tabulate over a DP array

Step 3: Collapse to two rolling variables

Step 4: Optimal O(1)-space scan

Step 5: Dry run

Step 6: Common mistakes and follow-ups

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity

FAQ

What is the time and space complexity of Min Cost Climbing Stairs?

What is the most efficient way to solve Min Cost Climbing Stairs?

How do you solve Min Cost Climbing Stairs in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Min Cost Climbing Stairs an easy or hard interview question?

See also

Min Cost Climbing Stairs – Solution & Complexity

Solution Walkthrough

1Step 1: Frame the recurrence

2Step 2: Tabulate over a DP array

3Step 3: Collapse to two rolling variables

4Step 4: Optimal O(1)-space scan

5Step 5: Dry run

6Step 6: Common mistakes and follow-ups

7Step 7: Edge cases to test mentally

8Step 8: Final full solution and complexity

FAQ

What is the time and space complexity of Min Cost Climbing Stairs?

What is the most efficient way to solve Min Cost Climbing Stairs?

How do you solve Min Cost Climbing Stairs in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Min Cost Climbing Stairs an easy or hard interview question?

See also

Step 1: Frame the recurrence

Step 2: Tabulate over a DP array

Step 3: Collapse to two rolling variables

Step 4: Optimal O(1)-space scan

Step 5: Dry run

Step 6: Common mistakes and follow-ups

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity