LeetCode 509 - Fibonacci Number

Difficulty: 🟢 Easy
Topics: Math, Dynamic Programming, Recursion, Memoization

Solution

Problem Understanding

This problem asks us to compute the nth Fibonacci number.

The Fibonacci sequence is defined recursively. The first two numbers are fixed:

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

Every value after that is calculated as the sum of the previous two values:

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

Given an integer n, we must return the value of F(n).

In other words, the input represents the position in the Fibonacci sequence, and the output is the number stored at that position.

For example:

n = 2 means we want the third Fibonacci number:

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

n = 4 means:

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

The constraints are very small:

0 <= n <= 30

This tells us several important things about the problem:

The maximum input size is tiny, so even slower solutions may still pass.
Since n never exceeds 30, recursion depth is not dangerous.
Integer overflow is not a concern because Fibonacci values remain small at this scale.

However, there are still efficiency considerations. A naive recursive solution recomputes the same subproblems many times, making it unnecessarily expensive.

Several edge cases are important:

n = 0, we must return 0 immediately.
n = 1, we must return 1.
Small values like n = 2 are easy places for off by one errors.
A recursive implementation without memoization may repeatedly calculate the same values, leading to poor performance.

The problem guarantees valid input, so we do not need to handle negative numbers or invalid types.

Approaches

Brute Force Approach, Plain Recursion

The most straightforward solution follows the Fibonacci definition directly.

To calculate F(n), we recursively calculate:

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

This mirrors the mathematical formula exactly. For example:

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

The issue is that many values are recalculated repeatedly. For example, F(3) may be computed multiple times during the same recursion tree.

Although this brute force approach is correct because it directly implements the recurrence relation, it is inefficient due to overlapping subproblems.

The time complexity becomes exponential because the recursion tree branches repeatedly.

Optimal Approach, Iterative Dynamic Programming

The key observation is that every Fibonacci number depends only on the previous two numbers.

Instead of recalculating earlier values repeatedly, we can build the sequence iteratively.

At any point, we only need:

The previous Fibonacci number
The Fibonacci number before that

This means we do not need an array or recursion. We can keep just two variables and update them as we move forward.

For example:

0, 1 → 1 → 2 → 3 → 5

Each new number is computed from the previous two.

This transforms the solution from exponential time into linear time while also reducing space usage to constant memory.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2ⁿ)	O(n)	Recursive solution repeatedly recomputes the same Fibonacci values
Optimal	O(n)	O(1)	Iterative dynamic programming using only two variables

Algorithm Walkthrough

Handle the base cases first.

If n is 0, return 0. If n is 1, return 1.

These cases are necessary because the Fibonacci sequence explicitly defines them, and they prevent unnecessary iteration. 2. Initialize two variables.

We maintain:

prev2 = 0, representing F(0)
prev1 = 1, representing F(1)

These values act as the rolling state for our computation. 3. Iterate from 2 through n.

At each step, calculate the next Fibonacci number:

current = prev1 + prev2

This follows the Fibonacci recurrence exactly. 4. Shift the variables forward.

After computing the new Fibonacci number:

prev2 = prev1
prev1 = current

This ensures the next iteration always has access to the two most recent Fibonacci values. 5. Return the final result.

After finishing the loop, prev1 contains F(n).

Why it works

The algorithm maintains an invariant throughout execution:

prev2 = F(i - 2)
prev1 = F(i - 1)

Before each iteration, these variables always represent the two previous Fibonacci numbers. Since Fibonacci numbers are defined as the sum of the two preceding numbers, computing:

current = prev1 + prev2

correctly produces F(i). Updating the variables preserves the invariant for the next iteration. By induction, the algorithm correctly computes F(n).

Python Solution

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

        if n == 1:
            return 1

        prev2 = 0
        prev1 = 1

        for _ in range(2, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

This implementation begins by handling the two base cases directly. Since F(0) and F(1) are predefined, returning immediately avoids unnecessary work.

After that, two variables are initialized. prev2 stores F(0) and prev1 stores F(1).

The loop runs from 2 to n, inclusive. During each iteration, current is calculated as the sum of the previous two Fibonacci numbers. Then the variables are shifted forward so they continue representing the latest two Fibonacci values.

Once the loop finishes, prev1 contains the answer and is returned.

This implementation is efficient because it avoids recursion and stores only the minimum information needed.

Go Solution

func fib(n int) int {
    if n == 0 {
        return 0
    }

    if n == 1 {
        return 1
    }

    prev2 := 0
    prev1 := 1

    for i := 2; i <= n; i++ {
        current := prev1 + prev2
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

The Go implementation follows the same logic as the Python version. Since Go uses explicit variable declarations, we initialize integers with :=.

There are no concerns about integer overflow for this problem because n <= 30, so Fibonacci values remain comfortably within Go's int range.

Unlike Python, Go does not have classes, so the solution is implemented as a standalone function matching the required LeetCode signature.

Worked Examples

Example 1: `n = 2`

We want to compute F(2).

Initial state:

Step	prev2	prev1	current
Start	0	1	-

Loop execution:

Iteration	Formula	current	prev2 After	prev1 After
i = 2	1 + 0	1	1	1

Final answer:

Example 2: `n = 3`

We want to compute F(3).

Initial state:

Step	prev2	prev1	current
Start	0	1	-

Loop execution:

Iteration	Formula	current	prev2 After	prev1 After
i = 2	1 + 0	1	1	1
i = 3	1 + 1	2	1	2

Final answer:

Example 3: `n = 4`

We want to compute F(4).

Initial state:

Step	prev2	prev1	current
Start	0	1	-

Loop execution:

Iteration	Formula	current	prev2 After	prev1 After
i = 2	1 + 0	1	1	1
i = 3	1 + 1	2	1	2
i = 4	2 + 1	3	2	3

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate from `2` to `n`, performing constant work per step
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs exactly one pass through the Fibonacci sequence up to n. Since each iteration uses constant time operations, the total running time grows linearly with n.

The space complexity is constant because we only store three integer variables, prev1, prev2, and current, regardless of input size.

Test Cases

solution = Solution()

assert solution.fib(0) == 0  # Minimum boundary case
assert solution.fib(1) == 1  # Second base case
assert solution.fib(2) == 1  # First computed Fibonacci value
assert solution.fib(3) == 2  # Small recursive progression
assert solution.fib(4) == 3  # Provided example
assert solution.fib(5) == 5  # Standard Fibonacci progression
assert solution.fib(10) == 55  # Medium sized input
assert solution.fib(20) == 6765  # Larger computation
assert solution.fib(30) == 832040  # Maximum constraint

Test	Why
`n = 0`	Verifies minimum boundary case
`n = 1`	Ensures second base case works correctly
`n = 2`	Confirms first computed Fibonacci value
`n = 3`	Verifies recurrence logic
`n = 4`	Matches provided example
`n = 5`	Tests normal sequence progression
`n = 10`	Validates medium sized input
`n = 20`	Ensures correctness for larger values
`n = 30`	Tests maximum constraint

Edge Cases

`n = 0`

This is the smallest valid input and an easy source of bugs. Some implementations accidentally start iteration immediately or assume Fibonacci begins at 1.

Our implementation explicitly checks:

if n == 0:
    return 0

This guarantees the correct result without entering the loop.

`n = 1`

The second base case can also be mishandled, especially if the loop begins from 2 without checking smaller values first.

Our implementation handles this separately:

if n == 1:
    return 1

This ensures correctness and avoids unnecessary computation.

Very Small Inputs Like `n = 2`

Small inputs often expose off by one errors in loops.

For example, if the loop range is incorrect, the algorithm might execute too many or too few iterations.

Our loop runs:

range(2, n + 1)

This guarantees that for n = 2, the loop executes exactly once, producing:

F(2) = 1

correctly.

LeetCode 509 - Fibonacci Number

Solution

Problem Understanding

Approaches

Brute Force Approach, Plain Recursion

Optimal Approach, Iterative Dynamic Programming

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1: n = 2

Example 2: n = 3

Example 3: n = 4

Complexity Analysis

Test Cases

Edge Cases

n = 0

n = 1

Very Small Inputs Like n = 2

Example 1: `n = 2`

Example 2: `n = 3`

Example 3: `n = 4`

`n = 0`

`n = 1`

Very Small Inputs Like `n = 2`