LogoKode$word
Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions
Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

Learn how to solve the Climbing Stairs problem using recursion, dynamic programming, and space optimization. Includes Java code, examples, and interview tips.

7 views
0
0
Github icon
Listen to articleAudio version

Introduction

The Climbing Stairs problem is one of the most commonly asked coding interview questions for beginners. It is a perfect example to understand recursion, memoization, and dynamic programming (DP).

In this article, we will break down the problem step by step and explore multiple approaches—from brute force recursion to an optimized space-efficient solution.

Link of Problem: LeetCode – Climbing Stairs

Problem Statement

You are climbing a staircase that has n steps.

  1. Each time, you can either climb 1 step or 2 steps.
  2. The goal is to calculate the total number of distinct ways to reach the top.

Example

Input:

n = 2

Output:

2

Explanation:

  1. 1 + 1
  2. 2

Input:

n = 3

Output:

3

Explanation:

  1. 1 + 1 + 1
  2. 1 + 2
  3. 2 + 1

Key Insight

To reach step n, there are only two possibilities:

  1. From step n-1 (taking 1 step)
  2. From step n-2 (taking 2 steps)

So, the recurrence relation becomes:

ways(n) = ways(n-1) + ways(n-2)

This is identical to the Fibonacci sequence, making this problem a classic DP question.

Approach 1: Recursive Solution (Brute Force)

Idea

Break the problem into smaller subproblems:

  1. Count ways to reach n-1
  2. Count ways to reach n-2
  3. Add both results

Code

class Solution {
public int climbStairs(int n) {
if(n == 0) return 1;
if(n < 0) return 0;
return climbStairs(n-1) + climbStairs(n-2);
}
}

Complexity

  1. Time Complexity: O(2^n)
  2. Space Complexity: O(n)

Drawback

This solution recalculates the same subproblems multiple times, leading to Time Limit Exceeded (TLE) for larger values.

Approach 2: Recursion with Memoization (Top-Down DP)

Idea

To optimize recursion, store already computed results using a HashMap.

  1. Avoid repeated calculations
  2. Convert exponential time into linear time

Code

import java.util.HashMap;

class Solution {
private HashMap<Integer, Integer> memo = new HashMap<>();

public int climbStairs(int n) {
if(n == 0) return 1;
if(n < 0) return 0;

if(memo.containsKey(n)) {
return memo.get(n);
}

int result = climbStairs(n-1) + climbStairs(n-2);
memo.put(n, result);

return result;
}
}

Complexity

  1. Time Complexity: O(n)
  2. Space Complexity: O(n)

Why It Works

Memoization ensures each subproblem is solved only once, making recursion efficient and practical.

Approach 3: Dynamic Programming (Bottom-Up)

Idea

Instead of recursion, build the solution iteratively:

  1. Use an array dp[]
  2. Store results for each step
  3. Build from smaller values to larger ones

Code

class Solution {
public int climbStairs(int n) {
if(n == 1) return n;
if(n == 2) return n;
if(n == 3) return n;

int dp[] = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;

for(int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}

return dp[n];
}
}

Complexity

  1. Time Complexity: O(n)
  2. Space Complexity: O(n)

Approach 4: Optimal Solution (Space Optimized)

Idea

We only need the last two values instead of the whole array.

Code

class Solution {
public int climbStairs(int n) {
if(n <= 2) return n;

int prev1 = 1;
int prev2 = 2;

for(int i = 3; i <= n; i++) {
int current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}

return prev2;
}
}

Complexity

  1. Time Complexity: O(n)
  2. Space Complexity: O(1)

Key Takeaways

  1. The problem follows a Fibonacci-like pattern
  2. Brute force recursion is simple but inefficient
  3. Memoization converts recursion into an efficient solution
  4. Dynamic programming avoids recursion completely
  5. Space optimization reduces memory usage to constant space

When This Problem Is Asked

This question is frequently asked in:

  1. Coding interviews (product-based companies)
  2. Data Structures & Algorithms exams
  3. Online coding platforms

It evaluates:

  1. Problem-solving ability
  2. Understanding of recursion
  3. Optimization skills

Conclusion

The Climbing Stairs problem is a foundational example for learning dynamic programming. Starting with recursion and improving it using memoization and iterative DP demonstrates how to optimize algorithms effectively.

Understanding this pattern will help solve many similar problems related to sequences and decision-making.

Frequently Asked Questions (FAQs)

1. Is this problem related to Fibonacci?

Yes, the recurrence relation is exactly the same as the Fibonacci sequence.

2. Why does recursion fail for large inputs?

Because it recalculates the same values repeatedly, leading to exponential time complexity.

3. What is the best approach?

The space-optimized approach is the most efficient with O(n) time and O(1) space.

Related Articles

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

Read Article
Sort Colors

Sort Colors

LeetCode question 75 Medium

Read Article
Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Learn how to solve the Subsets problem using recursion, backtracking, loops, and bit manipulation. Includes Java code, intuition, and complexity analysis.

Read Article
LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

Master the Monotonic Stack Pattern With HashMap Optimization — Step-by-Step Dry Run, Brute Force to O(n) Solution, and Full Complexity Analysis in Java

Read Article
Ai Assistant Kas