Climbing Stairs

📋

Problem

Imagine you are climbing a staircase with n steps, and you can take either 1 or 2 steps at a time. How many distinct ways can you reach the top?

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? Input: integer n (number of steps). Output: integer representing the number of distinct ways to reach the top.

1 ≤ n ≤ 10^5

Edge cases: n = 1 → 1 (only one way: single step)n = 2 → 2 (two ways: 1+1 or 2)n = 0 → 1 (one way: stand still, base case)

</>

IDE

def climb_stairs(n: int) -> int:public int climbStairs(int n)int climbStairs(int n)function climbStairs(n)

def climb_stairs(n):
    # Write your solution here
    pass

class Solution {
    public int climbStairs(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int climbStairs(int n) {
    // Write your solution here
    return 0;
}

function climbStairs(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Missing or incorrect base case for n=0 or n=1, returning 0 instead of 1.✅ Initialize ways(0)=1 and ways(1)=1 explicitly.

Wrong: Incorrect small integer less than expectedUsing greedy approach that counts only some sequences, missing others.✅ Implement full DP recurrence ways(n) = ways(n-1) + ways(n-2).

Wrong: Exponential time TLEUsing pure recursion without memoization or DP.✅ Use bottom-up DP or memoization to achieve O(n) time complexity.

Wrong: Off-by-one errors causing wrong countsIncorrect indexing or base case initialization.✅ Ensure ways(0)=1, ways(1)=1 and recurrence is applied correctly.

Wrong: Treating steps as 0/1 knapsack (one-time use)Confusing problem with 0/1 knapsack, limiting step reuse.✅ Allow unlimited reuse of 1 and 2 steps in recurrence.

✓

Test Cases

Make sure your base cases are correctly implemented before testing edge cases.

Review your approach for common pitfalls like greedy or incorrect step reuse.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"n":3}

Expected3

⏱ Performance - must finish in 2000ms

There are three ways: 1+1+1, 1+2, 2+1

💡 Think about how the number of ways to reach step n relates to previous steps.

💡 Use the recurrence: ways(n) = ways(n-1) + ways(n-2).

💡 Initialize base cases ways(0)=1 and ways(1)=1, then build up to n.

Why it failed: Returned incorrect count for n=3; likely missed adding ways(n-2). Fix by implementing ways(n) = ways(n-1) + ways(n-2). This is the canonical example test.

✓ Correctly computed ways for n=3 using Fibonacci-like DP.

t1_02basic

Input{"n":4}

Expected5

⏱ Performance - must finish in 2000ms

Ways to climb 4 steps: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2

💡 Extend the recurrence to n=4 using previous results.

💡 Check that ways(4) = ways(3) + ways(2).

💡 Calculate ways(2)=2 and ways(3)=3, sum to get 5.

Why it failed: Incorrect output for n=4; likely off-by-one or incorrect base cases. Fix by ensuring ways(0)=1 and ways(1)=1 and applying recurrence correctly.

✓ Correctly computed ways for n=4 using DP recurrence.

t2_01edge

Input{"n":0}

Expected1

⏱ Performance - must finish in 2000ms

Base case: standing still counts as one way to reach step 0.

💡 Consider what ways(0) should return as base case.

💡 ways(0) must be 1 to allow building up the recurrence.

💡 Set ways(0)=1 explicitly to handle n=0 input.

Why it failed: Returned 0 or error for n=0; missing base case ways(0)=1. Fix by initializing ways(0)=1.

✓ Correctly handled base case n=0 with ways=1.

t2_02edge

Input{"n":1}

Expected1

⏱ Performance - must finish in 2000ms

Only one way to climb 1 step: a single step.

💡 Check base case for n=1.

💡 ways(1) should be 1, not 0 or undefined.

💡 Initialize ways(1)=1 explicitly or handle n<=1 return 1.

Why it failed: Incorrect output for n=1; likely missing or wrong base case. Fix by returning 1 when n=1.

✓ Correctly returned 1 way for n=1.

t2_03edge

Input{"n":2}

Expected2

⏱ Performance - must finish in 2000ms

Two ways to climb 2 steps: 1+1 or 2.

💡 Verify ways(2) = ways(1) + ways(0).

💡 Ensure base cases ways(0)=1 and ways(1)=1 are correct.

💡 Calculate ways(2) = 1 + 1 = 2.

Why it failed: Incorrect output for n=2; likely incorrect recurrence or base cases. Fix by applying ways(2)=ways(1)+ways(0).

✓ Correctly computed ways for n=2.

t3_01corner

Input{"n":5}

Expected8

⏱ Performance - must finish in 2000ms

Ways to climb 5 steps: 8 distinct sequences.

💡 Check if your solution uses a greedy approach (e.g., always take 2 steps first).

💡 Greedy fails because it misses sequences with mixed 1 and 2 steps.

💡 Use DP recurrence ways(n) = ways(n-1) + ways(n-2) to count all sequences.

Why it failed: Output less than 8 for n=5; greedy approach misses some sequences. Fix by implementing full DP recurrence instead of greedy.

✓ Correctly counted all sequences including mixed steps.

t3_02corner

Input{"n":6}

Expected13

⏱ Performance - must finish in 2000ms

Ways to climb 6 steps: 13 distinct sequences.

💡 Check if your solution confuses 0/1 steps with unbounded steps.

💡 This problem allows unlimited 1 or 2 steps, not just one-time use.

💡 Apply Fibonacci recurrence without limiting step reuse.

Why it failed: Output incorrect for n=6; likely treating steps as 0/1 knapsack (one-time use). Fix by allowing unlimited reuse of steps in recurrence.

✓ Correctly handled unlimited step reuse.

t3_03corner

Input{"n":7}

Expected21

⏱ Performance - must finish in 2000ms

Ways to climb 7 steps: 21 distinct sequences.

💡 Check for off-by-one errors in indexing or base cases.

💡 Verify that ways(0)=1 and ways(1)=1 are correctly set.

💡 Ensure recurrence uses ways(n) = ways(n-1) + ways(n-2) without skipping steps.

Why it failed: Output incorrect for n=7; off-by-one error in base cases or recurrence. Fix by correctly initializing ways(0) and ways(1) and applying recurrence properly.

✓ Correctly handled indexing and base cases.

t4_01performance

Input{"n":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100000 to test O(n) DP solution completes within 2 seconds.

💡 Brute force recursion is O(2^n) and will time out here.

💡 Use bottom-up DP or space optimized DP with O(n) time complexity.

💡 Avoid recursion and memoization overhead for best performance.

Why it failed: Solution timed out on n=100000; likely using exponential recursion. Fix by implementing O(n) DP or iterative solution.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. You are given a circular street with houses arranged in a loop, each containing some amount of money. You want to maximize the amount you rob without robbing two adjacent houses, and since the street is circular, the first and last houses are also adjacent. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that always picks the house with the maximum money first

B. Dynamic programming by splitting the problem into two linear subproblems excluding either the first or last house

C. Brute force recursion checking all subsets of houses

D. Sorting houses by money and robbing every other house

Solution

1. Step 1: Understand circular adjacency constraint

   The first and last houses cannot both be robbed, so the problem is not a simple linear DP.

2. Step 2: Split into two linear problems

   By considering two cases--rob houses from first to second last, or from second to last--we reduce the circular problem to two linear House Robber problems solvable by DP.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Splitting into two linear DP subproblems handles circular adjacency correctly [OK]

Hint: Split circular problem into two linear DP cases [OK]

Common Mistakes:

• Assuming greedy or sorting works
• Trying to rob first and last house together
• Using brute force without pruning

2. What is the time and space complexity of the optimal dynamic programming solution for the unlimited transactions stock problem using the space-optimized state machine approach?

medium

A. Time: O(n^2), Space: O(n) due to nested loops and dp array

B. Time: O(n), Space: O(1) by tracking only current holding and not holding states

C. Time: O(n), Space: O(n) because of recursion stack in memoization

D. Time: O(2^n), Space: O(n) due to exponential recursion without memoization

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates once over the price list (length n), performing constant time operations per iteration -> O(n) time.

2. Step 2: Analyze space complexity

   Only two variables track states (holding, not_holding), no arrays or recursion stack -> O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant state variables confirms O(n) time and O(1) space [OK]

Hint: Space optimized DP uses constant space, not arrays or recursion [OK]

Common Mistakes:

• Confusing recursion stack space with iterative DP
• Assuming DP always uses O(n) space
• Mistaking nested loops for this linear solution

3. Consider the following buggy code for minimum cost climbing stairs. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line 4: Loop range starting at 2

B. Line 7: Returning prev1 instead of min(prev1, prev2)

C. Line 6: Updating prev2 and prev1

D. Line 3: Initialization of prev2 and prev1

Solution

1. Step 1: Understand final return logic

   The top can be reached from either last step or second last step, so minimum of prev1 and prev2 must be returned.

2. Step 2: Identify incorrect return

   Returning only prev1 ignores the possibility that prev2 might be cheaper, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return min(prev1, prev2) to cover both possible last steps [OK]

Hint: Return min of last two costs, not just last [OK]

Common Mistakes:

• Forgetting min at return
• Misinitializing base cases
• Incorrect loop boundaries

4. Suppose the decoding problem is modified so that digits can be reused multiple times in decoding (e.g., '111' can decode '1' three times independently). Which modification to the algorithm correctly accounts for this change?

hard

A. Keep the original DP but multiply counts by the number of reuse possibilities at each step

B. Use a greedy approach to pick the maximum reuse count at each position

C. Use the same DP but allow transitions from all previous indices, increasing complexity to O(n^2)

D. Use recursion without memoization to explore all reuse combinations

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means decoding at position i can come from any previous position, not just i-1 or i-2.

2. Step 2: Adjust DP transitions

   DP must consider all previous indices for valid decodings, increasing complexity to O(n^2).

3. Step 3: Evaluate other options

   Multiplying counts or greedy approaches do not correctly count all reuse combinations; recursion without memoization is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allowing reuse requires considering all previous states -> O(n^2) DP [OK]

Hint: Reuse means transitions from all previous indices -> O(n^2) DP [OK]

Common Mistakes:

• Trying to keep O(n) DP or using greedy for reuse

5. If the Jump Game II problem is modified so that you can reuse positions multiple times (i.e., cycles allowed), which approach correctly finds the minimum jumps without infinite loops?

hard

A. Use a breadth-first search (BFS) on the graph of positions to find shortest path

B. Use the original greedy approach as is, since it always finds minimum jumps

C. Use a brute force recursion exploring all paths without memoization

D. Use bottom-up DP ignoring cycles, assuming no repeated states

Solution

1. Step 1: Understand the impact of allowing cycles

   Allowing reuse of positions means cycles can occur, so greedy or naive DP may loop infinitely or give wrong answers.

2. Step 2: Identify correct approach

   BFS on the graph of positions treats each index as a node and edges as jumps, finding shortest path (minimum jumps) while avoiding infinite loops by tracking visited nodes.

3. Step 3: Why other options fail

   Greedy assumes no cycles and can fail. Brute force recursion without memoization causes infinite recursion. Bottom-up DP ignoring cycles may not terminate or produce incorrect results.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   BFS finds shortest path in graphs with cycles safely [OK]

Hint: Cycles require BFS with visited tracking to avoid infinite loops [OK]

Common Mistakes:

• Applying greedy blindly despite cycles
• Ignoring infinite recursion in brute force
• Assuming DP works without cycle checks