LeetCode 509: Fibonacci Number

Problem Restatement

The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1

For all n > 1:

$$ F(n)=F(n-1)+F(n-2) $$

We are given an integer n.

We need to return the value of F(n).

The official problem asks us to compute the nth Fibonacci number using the standard recurrence definition.

Input and Output

Item	Meaning
Input	An integer n
Output	The nth Fibonacci number
Base cases	F(0) = 0, F(1) = 1

Function shape:

class Solution:
    def fib(self, n: int) -> int:
        ...

Examples

Example 1:

n = 2

Using the recurrence:

F(2) = F(1) + F(0)
     = 1 + 0
     = 1

So the answer is:

1

Example 2:

n = 3

F(3) = F(2) + F(1)
     = 1 + 1
     = 2

So the answer is:

2

Example 3:

n = 4

F(4) = F(3) + F(2)
     = 2 + 1
     = 3

So the answer is:

3

First Thought: Direct Recursion

The definition itself naturally suggests recursion.

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

This directly follows the recurrence relation.

However, it recomputes the same values many times.

For example:

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)

The subtree fib(3) appears repeatedly.

Problem With Recursive Recalculation

The recursive solution performs overlapping work.

The same Fibonacci values are recomputed many times.

The running time grows exponentially:

O(2^n)

This becomes inefficient even for moderate values of n.

We need to reuse already computed results.

Key Insight

Each Fibonacci number depends only on the previous two numbers.

So instead of storing the entire sequence, we only need two variables:

Variable	Meaning
a	Previous Fibonacci number
b	Current Fibonacci number

At each step:

next = a + b

Then shift forward:

a = b
b = next

This is dynamic programming with constant memory.

Algorithm

Handle small values first:

if n <= 1:
    return n

Initialize:

a = 0
b = 1

These represent:

F(0), F(1)

Then repeat from 2 to n:

1. Compute the next Fibonacci value.
2. Shift the window forward.

Finally, return b.

Correctness

Initially:

a = F(0)
b = F(1)

At each iteration, the algorithm computes:

next = a + b

By the Fibonacci recurrence, this equals the next Fibonacci number.

Then the variables are updated:

a becomes the old b
b becomes the new Fibonacci number

So after every iteration:

a = F(i-1)
b = F(i)

When the loop finishes, b equals F(n).

Therefore the algorithm returns the correct Fibonacci number.

Complexity

Metric	Value	Why
Time	O(n)	One loop iteration per Fibonacci step
Space	O(1)	Only two variables are stored

Implementation

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        a = 0
        b = 1

        for _ in range(2, n + 1):
            a, b = b, a + b

        return b

Code Explanation

Small inputs are handled immediately:

if n <= 1:
    return n

Initialize the first two Fibonacci values:

a = 0
b = 1

Each iteration computes the next Fibonacci number:

a, b = b, a + b

This simultaneously updates both variables.

After the update:

a becomes the old current value
b becomes the next Fibonacci value

The loop continues until reaching F(n).

Finally:

return b

returns the answer.

Testing

def test_fib():
    s = Solution()

    assert s.fib(0) == 0
    assert s.fib(1) == 1
    assert s.fib(2) == 1
    assert s.fib(3) == 2
    assert s.fib(4) == 3
    assert s.fib(10) == 55

    print("all tests passed")

Test meaning:

Test	Why
0	First base case
1	Second base case
2	First recursive combination
3	Small transition case
4	Multiple iterations
10	Larger standard Fibonacci value