PPractick

The problem

You're building a step-counter mini-game for a fitness app. A user is climbing a staircase with n steps, and on each move they can climb either 1 step or 2 steps at a time. To gamify the experience, the app wants to show the user a fun stat: how many distinct ways they could have climbed to the top, given their choice of 1-or-2-step moves at each point. Your task: given n, compute the total number of distinct ways to reach the top.

Example: n = 3 → ways are [1,1,1], [1,2], [2,1] → 3 distinct ways.

Function signature

int climbStairs(int n);

Test cases

Input n	Output	Explanation
2	2	Ways: [1,1], [2]
3	3	Ways: [1,1,1], [1,2], [2,1]
1	1	Only one way: [1]
0	1	Trivially one way: take no steps (empty sequence)
4	5	Ways: [1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]
5	8	Fibonacci-like growth: 8 distinct ways
10	89	Matches Fibonacci sequence pattern

(Confirm: n is non-negative; n=0 is typically defined as having exactly 1 way — the "do nothing" path — but always verify with the interviewer.)

How interviewers phrase it

• "You're climbing a staircase of n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?"
• This is the quintessential intro-to-DP problem (LeetCode 70), almost always used as a warm-up before moving to cost-based or constraint-based variants like Frog Jump or House Robber.
• Interviewers may frame it as "count paths" or directly reference Fibonacci to see if you spot the connection yourself, or want you to derive it independently.

Clarifying questions to ask

1. Can you climb only 1 or 2 steps at a time, never more, never 0? Confirm the exact step set.
2. What should the answer be for n = 0? (Convention: 1, representing the single "already there" way — confirm this isn't ambiguous in their expected test cases.)
3. Is n guaranteed non-negative? What's the expected upper bound — does it suggest recursion depth or overflow concerns (Fibonacci numbers grow exponentially)?
4. Do you want the count only, or do you also need to enumerate/print all the actual paths? (Enumerating all paths is exponential and a very different problem.)

Follow-ups to expect

1. "Can you solve this with O(1) space?"
2. "What if you could climb 1, 2, or 3 steps at a time?"
3. "What if there's a cost associated with each step (Min Cost Climbing Stairs)?"
4. "Can you compute this in O(log n) time using matrix exponentiation?"
5. "What if some steps are broken/blocked and can't be landed on?"
6. "Can you solve it with plain recursion, and why is that inefficient?"

Related questions

• Kadane's Algorithm Medium
• Print subarray with maximum subarray sum Medium
• Maximum Product Subarray in an Array Medium
• Longest Palindromic Substring Medium
• Frog Jump Medium
• Frog jump with K distances Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in