Nth Fibonacci Number

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}