LeetCode 509: Fibonacci Number

Problem Restatement

The Fibonacci sequence is defined as:

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

For all n > 1:

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

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:

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

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: