509. Fibonacci Number

Problem¶

Given \(n\), return the Fibonacci number defined by:

Input:  n = 6
State:  0, 1, 1, 2, 3, 5, 8
Output: 8

Key trick¶

Keep only the previous two Fibonacci numbers because every new value depends solely on them.

Trap¶

• Naive recursion takes exponential time.
• Loop boundaries often cause off-by-one errors.
• Forgetting that n = 0 must return 0.

Why is it interesting?¶

It is the simplest example of reducing dynamic programming from an entire table to constant space.

Python solution¶

class Solution:
    def fib(self, n: int) -> int:
        # After each iteration, prev1 is the next Fibonacci number.
        prev2, prev1 = 0, 1

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

        return prev2

• Time complexity: \(O(n)\)
• Space complexity: \(O(1)\)

Comment on my solution¶

Your solution is correct, idiomatic, and optimal at \(O(n)\) time and \(O(1)\) space. The explicit base case makes range(n - 1) safe and keeps the loop invariant straightforward.

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

        prev2, prev1 = 0, 1
        for _ in range(n - 1):
            prev2, prev1 = prev1, prev1 + prev2

        return prev1