#509 Fibonacci Number
frequently reported atTCSMicrosoftBloombergAmazonGoogleApple
the problem
In plain words
The Fibonacci sequence starts 0, 1 and each later term is the sum of the two before it (0, 1, 1, 2, 3, 5, …). Return the n-th term, counting from F(0) = 0.
in n = 2
out 1
F(2) = F(1) + F(0) = 1 + 0.
in n = 3
out 2
F(3) = F(2) + F(1) = 1 + 1.
in n = 4
out 3
0, 1, 1, 2, 3.
- 0 ≤ n ≤ 30
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternRecursion on a smaller input1D DP
The definition is a recursion — but it repeats sub-problems. Cache each F(k) once, or just keep the last two values in a loop.
solutions
From brute force to optimal
Translate the formula literally: two recursive calls per n.
- If n ≤ 1, return n.
- Otherwise return fib(n − 1) + fib(n − 2).
Each call branches into two; the tree has about φⁿ ≈ 1.618ⁿ nodes (fib(30): 2.7 million calls).
The deepest path fib(n) → fib(n−1) → … → fib(1) has n frames.
class Solution { public int fib(int n) { if (n <= 1) return n; // F(0) = 0, F(1) = 1 return fib(n - 1) + fib(n - 2); // two calls → the tree doubles }}Watch the tree explode
Same recursion, but store each answer in memo[k] and return it on later calls.
- memo filled with −1.
- Base case n ≤ 1.
- If memo[n] is set, return it.
- Otherwise compute, store, return.
Each value 2..n is computed once; every other call is an O(1) lookup (2n − 1 calls).
The memo array plus a recursion depth of n.
class Solution { public int fib(int n) { int[] memo = new int[n + 1]; Arrays.fill(memo, -1); // -1 means "not solved yet" return solve(n, memo); } private int solve(int n, int[] memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; // solved before → reuse memo[n] = solve(n - 1, memo) + solve(n - 2, memo); return memo[n]; }}Memo in action
Build up from F(0), F(1), keeping only the last two values.
- prev = 0, curr = 1.
- Repeat n − 1 times: next = prev + curr; shift both forward.
- Return curr.
One loop of n − 1 additions.
Only three ints, no stack frames.
class Solution { public int fib(int n) { if (n <= 1) return n; int prev = 0, curr = 1; // F(0), F(1) for (int i = 2; i <= n; i++) { int next = prev + curr; prev = curr; curr = next; } return curr; }}in the room
How to say it in the interview
talk track
- Write the naive recursion first and say its cost: O(2ⁿ), because sub-problems repeat.
- Point to a repeat in the tree (fib(2) appears many times) → memoize → O(n) time and space.
- Notice each value only needs the previous two → loop with two variables → O(1) space.
traps
- Returning 1 for n = 0 (F(0) is 0).
- For larger n, F(47) overflows
int— uselongor mention it.
what they ask next
Follow-ups
Can you do better than O(n)?
Yes: matrix exponentiation of [[1,1],[1,0]] with fast power gives O(log n) — the same halving trick as Pow(x, n).
Climbing Stairs (LC 70)?
Same recurrence: ways(n) = ways(n−1) + ways(n−2), with ways(0) = ways(1) = 1.
before you submit
Edge cases to test
- n = 0 → 0 (not 1).
- n = 1 → 1.
- n = 30 → 832,040: naive recursion makes about 2.7 million calls — it passes once, but it's the wrong habit.
practise next
Similar problems
- #70Climbing StairsEasyin Dynamic Programming
- #198House RobberMediumin Dynamic Programming