DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Climbing Stairs

EasyDynamic ProgrammingRecursion
AmazonAdobeGoogle Community-reported practice tags — not verified company questions.

1Problem statement

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?

2Examples

Input: n = 2
Output: 2
Explanation: 1+1, 2
Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1
Input: n = 5
Output: 8

3Constraints

  • 1 ≤ n ≤ 45

4Approaches

Approach 1

Brute Force: Plain recursion

ways(n) = ways(n−1) + ways(n−2) without caching — recomputes the same subproblems.

Time O(2ⁿ)Space O(n)

Approach 2

Better: Memoization / tabulation

Store ways(k) for every k in an array.

Time O(n)Space O(n)

Approach 3

Optimal: Two variables

Only the last two values are needed — keep them in two variables (Fibonacci).

Time O(n)Space O(1)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1;
  let prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

for (const n of [2, 3, 5]) console.log(climbStairs(n));

6Complexity

Time

O(n)

Space

O(1)

7Visual walkthrough

  1. 1.ways(1) = 1, ways(2) = 2
  2. 2.ways(3) = 2 + 1 = 3
  3. 3.ways(4) = 3 + 2 = 5
  4. 4.ways(5) = 5 + 3 = 8

8Related questions

Maximum Subarray (Kadane's Algorithm)

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions