Fibonacci Number
Compute the nth Fibonacci number bottom-up in O(n) time and O(1) space by keeping only the last two values, instead of exponential recursion.
Problem Understanding
Fibonacci Number: F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2) for n > 1. Given n, return F(n).
Example: n = 4 returns 3: the sequence is 0, 1, 1, 2, 3.
The Intuition: Compute Each Value Once
Fibonacci is the textbook entry to dynamic programming.
- Plain recursion follows the definition directly, but
fib(n − 1)andfib(n − 2)both recomputefib(n − 3), and so on: exponential time. - Memoization or a table computes each F(i) once: O(n).
- Two variables are enough, because F(i) only looks back two steps: O(1) space.
The same "previous two values" recurrence drives Climbing Stairs, Min Cost Climbing Stairs and House Robber.
Interactive Walkthrough
The values F(0) to F(n) fill left to right. Only a and b are kept; older values grey out because the two-variable solution no longer needs them. Try n = 20 to see 6765 reached in 19 additions.
Dry Run Table
Input: n = 6
| i | a (F(i−2)) | b (F(i−1)) | F(i) = a + b |
|---|---|---|---|
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 3 |
| 5 | 2 | 3 | 5 |
| 6 | 3 | 5 | 8 |
Answer: 8.
The Solution Template
Bottom-up with two variables.
Fibonacci Number Code
1var fib = function(n) {2 if (n < 2) return n;3 let a = 0, b = 1;4 for (let i = 2; i <= n; i++) {5 [a, b] = [b, a + b];6 }7 return b;8};
Edge Cases & Common Mistakes
- n = 0 and n = 1: return n directly; the loop never runs.
- Updating a before using it:
a = b; b = a + bdoubles b; use a temporary or a simultaneous assignment. - Plain recursion in an interview: correct but exponential; mention memoization or the iterative version.
- Overflow: LeetCode limits n to 30, but F(47) already overflows a 32-bit int.
- Matrix power: F(n) can be computed in O(log n) with fast exponentiation of [[1, 1], [1, 0]], useful for very large n.
Summary
Return n for the base cases. Otherwise keep a = F(i − 2) and b = F(i − 1), and replace them with (b, a + b) until reaching n. Each value is computed once: O(n) time and O(1) space, instead of exponential recursion.
More practice: DSA interview questions with answers · patterns cheat sheet