Climbing Stairs - Practice Coding Problems

Climbing Stairs - Problem

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?

Note: Given n will be a positive integer.

Input & Output

Example 1 — Small Staircase

$ Input: n = 2

› Output: 2

💡 Note: There are two ways to climb to the top: 1. 1 step + 1 step, 2. 2 steps

Example 2 — Medium Staircase

$ Input: n = 3

› Output: 3

💡 Note: There are three ways: 1. 1+1+1 steps, 2. 1+2 steps, 3. 2+1 steps

Example 3 — Single Step

$ Input: n = 1

› Output: 1

💡 Note: Only one way to climb 1 step: take 1 step

Constraints

1 ≤ n ≤ 45

Visualization

Tap to expand

Understanding the Visualization

Input

Number of steps n to reach the top

Process

Count all possible combinations of 1-step and 2-step moves

Output

Total number of distinct ways

Key Takeaway

🎯 Key Insight: This is the Fibonacci sequence in disguise - each step count equals the sum of the previous two step counts

Asked in

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

The key insight is recognizing this follows the Fibonacci pattern: to reach step n, you can come from step n-1 (take 1 step) or step n-2 (take 2 steps). Best approach is space-optimized DP using two variables. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming (Bottom-Up)	O(n)	O(n)	Build solution iteratively from base cases
Brute Force Recursion	O(2ⁿ)	O(n)	Recursively explore all possible step combinations
Memoization (Top-Down DP)	O(n)	O(n)	Cache recursive results to avoid repeated calculations
Space-Optimized DP	O(n)	O(1)	Use only two variables instead of full array

Dynamic Programming (Bottom-Up) — Algorithm Steps

Create DP array with base cases
Iterate from 3 to n
For each position, dp[i] = dp[i-1] + dp[i-2]
Return dp[n]

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Cases

Initialize dp[1]=1, dp[2]=2

Fill Array

For each i: dp[i] = dp[i-1] + dp[i-2]

Result

Return dp[n]

Code -

solution.c — C

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

int solution(int n) {
    if (n <= 2) {
        return n;
    }
    
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    int result = dp[n];
    free(dp);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop from 3 to n, each iteration does constant work

✓ Linear Growth

Space Complexity

O(n)

DP array of size n+1 to store results for each step

⚡ Linearithmic Space

311.5K Views

Very High Frequency

~15 min Avg. Time

8.4K 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

Dynamic Programming (Bottom-Up) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler