LeetCode 70 – Climbing Stairs | Optimized Python Solution (O(1) Space)

Problem Overview

LeetCode 70, Climbing Stairs, is a classic dynamic programming problem. You are given an integer n representing the number of steps to reach the top. At each step, you can either climb 1 step or 2 steps. The task is to find the total number of distinct ways to reach the top.

---

Key Observation

To reach step n, you can come from:

• Step n - 1 (taking 1 step)
• Step n - 2 (taking 2 steps)

This leads to the recurrence relation:

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

This is exactly the same pattern as the Fibonacci sequence.

---

Base Cases

• n = 1 → 1 way
• n = 2 → 2 ways

For values greater than 2, we compute the answer iteratively.

---

Optimized Approach (O(1) Space)

Instead of storing all previous results in an array, we only keep track of the last two values. This reduces space complexity while keeping the logic efficient.

Python Code

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        
        i = 1
        j = 2
        for _ in range(3, n + 1):
            result = i + j
            i = j
            j = result

        return result

---

Step-by-Step Explanation

• i stores the number of ways to reach step n-2
• j stores the number of ways to reach step n-1
• Each iteration computes the next step using their sum

This efficiently builds the solution from the bottom up.

---

Complexity Analysis

Metric	Value
Time Complexity	O(n)
Space Complexity	O(1)

---

Why This Approach Is Optimal

• No recursion overhead
• No extra memory for DP arrays
• Fast and interview-friendly

---

Source Code

You can find the complete implementation here:

👉 GitHub – LeetCode 70 Python Solution

---

Tip: This problem is frequently asked in interviews to test understanding of dynamic programming optimization.