LeetCode 509: Fibonacci Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 509: Fibonacci Number?

In LeetCode 509: Fibonacci Number, you’re given an integer n, and your task is to return the nth number in the Fibonacci sequence, where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. For example, F(4) = 3 because the sequence is 0, 1, 1, 2, 3. This problem introduces recursion and iteration, related to LeetCode 70: Climbing Stairs, which uses similar principles.

Problem Statement

• Input: Integer n (non-negative).
• Output: Integer—the nth Fibonacci number.
• Rules: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).

Constraints

• 0 <= n <= 30

Examples

• Input: 2
• Output: 1
• Sequence: 0, 1, 1 → F(2) = 1.
• Input: 3
• Output: 2
• Sequence: 0, 1, 1, 2 → F(3) = 2.
• Input: 4
• Output: 3
• Sequence: 0, 1, 1, 2, 3 → F(4) = 3.

Understanding the Problem: Climbing the Fibonacci Ladder

To solve LeetCode 509: Fibonacci Number in Python, we need a function that computes the nth Fibonacci number efficiently. The sequence starts with F(0) = 0 and F(1) = 1, then builds by adding the previous two numbers. A naive recursive approach might call F(n-1) and F(n-2) repeatedly, but with n up to 30, that’s too slow. We’ll explore:

• Best Solution (Iterative): O(n) time, O(1) space—fast and lean.
• Alternative Solution (Recursive with Memoization): O(n) time, O(n) space—elegant but uses more memory.

Let’s dive into the iterative solution with a friendly breakdown!

Best Solution: Iterative Approach with O(1) Space

Why Iterative Is the Best

The iterative approach is the top choice for LeetCode 509 because it’s both time-efficient (O(n)) and space-efficient (O(1)). It uses a simple loop with two variables to track the previous numbers, avoiding the overhead of recursion or extra storage. It’s like climbing the Fibonacci ladder one step at a time, carrying only what you need!

How It Works

Think of this as a number-building dance:

• Step 1: Base Cases:
• If n = 0, return 0.
• If n = 1, return 1.
• Step 2: Iterate:
• Start with prev = 0, curr = 1.
• For each step from 2 to n, update:
• next = prev + curr.
• Shift: prev = curr, curr = next.
• Step 3: Return:
• After n steps, curr is F(n).
• Why It Works:
• Only keeps the last two numbers.
• Builds the sequence linearly.

It’s like a Fibonacci two-step!

Step-by-Step Example

Example: n = 4

• Init: prev = 0, curr = 1.
• Step 1: n > 1, proceed.
• Step 2: Iterate from 2 to 4:
• i = 2: next = 0 + 1 = 1, prev = 1, curr = 1.
• i = 3: next = 1 + 1 = 2, prev = 1, curr = 2.
• i = 4: next = 1 + 2 = 3, prev = 2, curr = 3.
• Step 3: curr = 3.
• Result: 3.

Example: n = 2

• Init: prev = 0, curr = 1.
• Step 1: n = 2.
• Step 2: i = 2: next = 0 + 1 = 1, prev = 1, curr = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def fib(self, n: int) -> int:
        # Step 1: Handle base cases
        if n == 0:
            return 0
        if n == 1:
            return 1

        # Step 2: Initialize variables
        prev, curr = 0, 1

        # Step 3: Iterate from 2 to n
        for i in range(2, n + 1):
            next_val = prev + curr  # Compute next Fibonacci
            prev = curr             # Shift prev forward
            curr = next_val         # Shift curr forward

        # Step 4: Return the nth number
        return curr

• Lines 4-7: Base cases: F(0) = 0, F(1) = 1.
• Line 10: Start with F(0) and F(1).
• Lines 13-16: Loop n-1 times:
• Add prev and curr for next value.
• Update prev and curr for next iteration.
• Line 19: curr holds F(n).
• Time Complexity: O(n)—n iterations.
• Space Complexity: O(1)—just two variables.

It’s like a Fibonacci conveyor belt!

Alternative Solution: Recursive with Memoization

Why an Alternative Approach?

The recursive solution with memoization computes F(n) by breaking it into F(n-1) and F(n-2), caching results to avoid redundant calls. It’s O(n) time and O(n) space—elegant and a great intro to dynamic programming in Python, though less space-efficient than iteration.

How It Works

Picture this as a recursive climb:

• Step 1: Base cases—F(0) = 0, F(1) = 1.
• Step 2: Recurse with memoization:
• F(n) = F(n-1) + F(n-2).
• Store results in a cache.
• Step 3: Return cached or computed value.

It’s like climbing with a memory aid!

Step-by-Step Example

Example: n = 4

• Init: memo = {0: 0, 1: 1}.
• Call: fib(4):
• fib(3) + fib(2):
• fib(3): fib(2) + fib(1):
• fib(2): fib(1) + fib(0) = 1 + 0 = 1, memo[2] = 1.
• fib(1) = 1.
• 1 + 1 = 2, memo[3] = 2.
• fib(2) = 1 (cached).
• 2 + 1 = 3, memo[4] = 3.
• Result: 3.

Code for Recursive Approach

class Solution:
    def fib(self, n: int) -> int:
        # Step 1: Memoization cache
        memo = {0: 0, 1: 1}

        # Step 2: Recursive helper
        def fib_helper(n):
            if n in memo:
                return memo[n]

            memo[n] = fib_helper(n-1) + fib_helper(n-2)
            return memo[n]

        # Step 3: Call and return
        return fib_helper(n)

• Line 4: Cache with base cases.
• Lines 7-11: Recursive function:
• Return cached value if exists.
• Compute, cache, and return.
• Line 14: Start recursion.
• Time Complexity: O(n)—each n computed once.
• Space Complexity: O(n)—memo dictionary.

It’s a memoized Fibonacci climber!

Comparing the Two Solutions

• Iterative (Best):
• Pros: O(n) time, O(1) space, simple.
• Cons: Less “fancy.”
• Recursive with Memoization (Alternative):
• Pros: O(n) time, elegant DP intro.
• Cons: O(n) space, recursion overhead.

Iterative wins for efficiency!

Additional Examples and Edge Cases

• 0: 0.
• 1: 1.
• 30: 832040.

Iterative handles them all!

Complexity Recap

• Iterative: Time O(n), Space O(1).
• Recursive: Time O(n), Space O(n).

Iterative’s the lean champ!

Key Takeaways

• Iteration: Simple and fast—learn at Python Basics!
• Memoization: Recursion with memory.
• Fibonacci: Classic sequence fun.
• Python: Loops or recursion, your pick!

Final Thoughts: Climb the Sequence!

LeetCode 509: Fibonacci Number in Python is a timeless challenge. The iterative approach is your quick path, while recursive memoization adds flair. Want more? Try LeetCode 70: Climbing Stairs or LeetCode 1137: N-th Tribonacci Number. Ready to count? Head to Solve LeetCode 509 on LeetCode and find that nth Fibonacci today!