Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Iterate with two variables `a = 0`, `b = 1`, updating `(a, b) → (b, a + b)` n times. O(n) time, O(1) space — far better than naive recursion's O(2ⁿ).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you avoid exponential recursion and recognise the O(1)-space rolling pattern.
Where candidates slip
Exponential recursion, or an off-by-one returning the wrong index.
How to stand out
Mention memoised recursion, the O(1) roll, and even the O(log n) matrix-power method.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Iterative two-variable roll
1Hint 1Explore hintHide hint
Each value needs only the previous two. Do you really need an array?
2Hint 2Explore hintHide hint
Roll two variables forward: (a, b) becomes (b, a + b).
3Hint 3Explore hintHide hint
Avoid naive recursion — it's exponential. Watch overflow past F(90).
A · Core idea
Each Fibonacci number is the sum of the previous two, so you only ever need to remember the last two values. Roll a pair (a, b) forward n times: (a, b) → (b, a + b). O(n) time, O(1) space.
Why not plain recursion. The naive fib(n) = fib(n-1) + fib(n-2) recomputes the same subproblems exponentially — fib(50) makes ~2.5 billion calls. The iterative roll computes each value once. Naming that O(2ⁿ) blow-up and replacing it with O(n) is the entire interview signal.
Why two variables suffice. The recurrence has 'order 2' — the next value depends only on the two before it. Whenever state depends on the last k values, you keep k variables, not the whole history. This is the seed of space-optimised dynamic programming.
Overflow. Fibonacci grows ~1.618ⁿ, so F(91) overflows 64-bit long. With long, n ≤ 90 is the safe range — beyond that you'd need BigInteger.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 6start
a=0, b=1
F(0)=08C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Naming the recursion's O(2ⁿ) cost and then giving the O(n) loop is the standout move on this classic.
ComplexityO(n) time, O(1) space — one addition per step for n steps, holding just two values.
E · Edge cases and pitfalls5n = 0 — Loop runs zero times; returns a = 0 = F(0).Explore edge casesHide edge cases
Edge cases handled
n = 0Loop runs zero times; returns a = 0 = F(0).n = 1One step → a = 1 = F(1).n = 90Largest F that fits in long; F(91) overflows.
Pitfalls
- Using naive recursion and timing out at O(2ⁿ).
- Off-by-one in the loop bound or returning b instead of a.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long fib(int n) { long a = 0, b = 1; for (int i = 0; i < n; i++) { long next = a + b; a = b;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Naive exponential recursion
fib(n-1)+fib(n-2) recomputes overlapping subproblems, making ~2ⁿ calls; fib(50) is already billions.
Explore the code comparisonHide the code comparison
Naive exponential recursion
fib(n-1)+fib(n-2) recomputes overlapping subproblems, making ~2ⁿ calls; fib(50) is already billions.
Don't write this
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2) # O(2^n)Write this instead
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n), O(1)Revise
Carry the pattern into the interview
Pattern to remember
Rolling two variables
Code pattern to memorize
a,b = 0,1; repeat n times: a,b = b, a+b; return aRules to remember
- 1Start a=0, b=1.
- 2Update (a,b)→(b,a+b) n times.
- 3Return a.
Use this pattern when
- State depends on the last k values
- Space-optimising a 1-D DP
Choose another pattern when
- Need many arbitrary indices fast — consider matrix power / closed form
Interview takeaway
When state depends on the last k values, keep k variables, not an array.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: Rolling two variables. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Climbing StairsComing soonIdentical recurrence — ways(n) = ways(n-1) + ways(n-2).
- Fibonacci in O(log n)Coming soonMatrix exponentiation of [[1,1],[1,0]].