Beginner LevelData Structures & Algorithms
What is the space-optimised Fibonacci solution?
ā Interview Prompt: Reduce Fibonacci DP from O(N) to O(1) space by keeping only the last two values in a rolling variable.
Standard bottom-up Fibonacci DP creates an $O(N)$ table. But since $F(N) = F(N-1) + F(N-2)$, we only need the last two values at any time.
By using two rolling variables we reduce space to $O(1)$ while keeping time at $O(N)$.
Code Implementation Example
typescript
function fibonacci(n: number): number {
if (n <= 0) return 0;
if (n === 1) return 1;
let a = 0, b = 1;
for (let i = 2; i <= n; i++) {
const next = a + b;
a = b;
b = next;
}
return b;
}
// Alternatively using destructuring:
function fib(n: number): number {
let [a, b] = [0, 1];
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}š”O(N) time, O(1) space Fibonacci with rolling variables.
šÆ Interview Key Takeaway
Space optimisation by rolling variables is a key DP technique. Whenever the recurrence only references the last K states, you can reduce space from O(N) to O(K).
#DSA#Fibonacci#Dynamic Programming#Space Optimisation#Beginner
Back to all Data Structures & Algorithms Questionsā