Min Cost Climbing Stairs - Practice Coding Problems

Min Cost Climbing Stairs - Problem

You are given an integer array cost where cost[i] is the cost of the i-th step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Input & Output

Example 1 — Basic Case

$ Input: cost = [10, 15, 20]

› Output: 15

💡 Note: You can start at index 1 (cost 15) and jump directly to the top, avoiding the more expensive paths through step 0 or step 2.

Example 2 — Multiple Steps

$ Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

› Output: 6

💡 Note: Start at index 0, jump to index 2, then 4, 6, 8, and finally to the top. Total cost: 1+1+1+1+1+1 = 6.

Example 3 — Minimum Size

$ Input: cost = [5, 10]

› Output: 5

💡 Note: Start at index 0 (cost 5) and jump directly to the top, which is cheaper than starting at index 1 (cost 10).

Constraints

2 ≤ cost.length ≤ 1000
0 ≤ cost[i] ≤ 999

Visualization

Tap to expand

Understanding the Visualization

Input

Array of step costs, can start from index 0 or 1

Process

At each step, choose cheaper of two previous paths

Output

Minimum cost to reach beyond the last step

Key Takeaway

🎯 Key Insight: At each step, we only need to consider the cheaper of the two previous steps to build the optimal solution

Asked in

a Amazon 45 G Google 38 M Microsoft 32 🍎 Apple 28

The key insight is that at each step, we choose the cheaper of the two previous steps. The space-optimized DP approach is optimal with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Space-Optimized DP	O(n)	O(1)	Use only two variables instead of full DP array
Memoization (Top-Down DP)	O(n)	O(n)	Cache recursive results to avoid recalculation
Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible paths recursively
1D Dynamic Programming	O(n)	O(n)	Bottom-up DP with array to store minimum costs

Space-Optimized DP — Algorithm Steps

Use two variables to track previous two minimum costs
Update variables as we iterate through the array
Return minimum of the two final values

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set first=cost[0], second=cost[1]

Iterate

Update variables: current = cost[i] + min(first, second)

Shift

Move values: first=second, second=current

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* cost, int size) {
    if (size <= 2) {
        return cost[0] < cost[1] ? cost[0] : cost[1];
    }
    
    int first = cost[0];
    int second = cost[1];
    
    for (int i = 2; i < size; i++) {
        int current = cost[i] + (first < second ? first : second);
        first = second;
        second = current;
    }
    
    return first < second ? first : second;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int cost[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            cost[size++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    printf("%d\n", solution(cost, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the cost array

✓ Linear Growth

Space Complexity

O(1)

Only uses two variables regardless of input size

✓ Linear Space

85.0K Views

High Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Space-Optimized DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler