Is Climbing Stairs easy or hard?

Climbing Stairs is classified as an Easy problem on LeetCode. The challenge mainly tests whether you recognize the Fibonacci-style recurrence and convert it into a dynamic programming or memoized recursion solution.

Climbing Stairs Python/Java solution

The typical Python or Java solution uses a loop with two variables representing the previous two steps. At each iteration compute current = prev1 + prev2, then shift the variables forward. This implements the Fibonacci recurrence in O(n) time and O(1) space.

How to solve Climbing Stairs in O(n)?

Use a Fibonacci-style dynamic programming approach. Initialize base values for 1 and 2 stairs, then iterate from 3 to n computing dp[i] = dp[i-1] + dp[i-2]. Each step is computed once, resulting in O(n) time and O(1) space when only the last two values are stored.

What is the best approach for Climbing Stairs?

The dynamic programming approach is considered the best solution. It uses the recurrence ways(n) = ways(n-1) + ways(n-2) and computes results iteratively in O(n) time. With a small optimization that keeps only the last two states, the space complexity can be reduced to O(1).

Is Climbing Stairs asked at Google/Amazon/Meta?

Climbing Stairs is a common entry-level dynamic programming problem frequently used in coding interviews. Variants of this problem appear at companies like Amazon, Google, and Meta to test understanding of recursion, memoization, and DP patterns.

What data structure is used in Climbing Stairs?

Most implementations use an array or list for the DP table to store intermediate results. In the optimized version, only two variables are needed because each state depends only on the previous two values.

What is the time complexity of Climbing Stairs?

The optimal dynamic programming and memoized recursion solutions both run in O(n) time because each stair state is computed exactly once. A naive recursive implementation without memoization would take O(2^n) time due to repeated subproblem calculations.

Description Hints 1 Solution Video 18:08

70. Climbing Stairs

Easy54.0% acceptance37 companies

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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Asked at top 20 of 37 companies

Deloitte Medianet AMD Hpe Zoho Adobe Accenture Grammarly Rakuten HSBC Bloomberg

Infosys

+8 more

Google Amazon Microsoft Meta Tiktok Apple Qualcomm Cognizant

Topics

Hints open one at a time

Hint 1

To reach nth step, what could have been your previous steps? (Think about the step sizes)

18:08

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution