Nth Fibonacci Number
Problem
Return the nth Fibonacci number, where F(0) = 0, F(1) = 1 and F(n) = F(n−1) + F(n−2). It is the standard way to show naive recursion → memoisation → tabulation → O(1) space.
Example 1
Input: n = 10 Output: 55
Also asked as: fibonacci
Test cases
Case 1
Input: 10 Expected: 55
Case 2
Input: 20 Expected: 6765
Case 3
Input: 2 Expected: 1
Case 4
Input: 1 Expected: 1
Case 5
Input: 0 Expected: 0
View solutionHide solution4 approaches
1. Naive recursion
Time O(2ⁿ)Space O(n)
Direct definition. Recomputes the same subproblems — exponential. State this only as the starting point.
const fib = (n) => (n < 2 ? n : fib(n - 1) + fib(n - 2));2. Top-down memoisation
Time O(n)Space O(n)
Cache each fib(k) the first time it is computed.
function fib(n, memo = new Map()) { if (n < 2) return n; if (memo.has(n)) return memo.get(n); const v = fib(n - 1, memo) + fib(n - 2, memo); memo.set(n, v); return v;}3. Bottom-up table
Time O(n)Space O(n)
Fill dp[0..n] iteratively — no recursion, no stack.
function fib(n) { const dp = [0, 1]; for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n];}4. Two rolling variables
Time O(n)Space O(1)
Only the last two values matter — O(1) space.
function fib(n) { let a = 0, b = 1; for (let i = 0; i < n; i++) [a, b] = [b, a + b]; return a;}