Leetcode – Fibonacci Number Solution in Python

Spread the love

Introduction

The Fibonacci sequence is a classic topic in mathematics and computer science. It often serves as an introductory problem for recursion and dynamic programming. On Leetcode, the Fibonacci Number problem poses an engaging challenge that invites you to apply your knowledge of algorithms and data structures. In this exhaustive article, we will dissect the Fibonacci Number problem, understand the underlying mathematical concepts, and explore various approaches to solving it using Python.

The Fibonacci Number problem on Leetcode is as follows:

Given n, calculate F(n), where F(n) is the n-th Fibonacci number. The Fibonacci numbers are defined as

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2) for n > 1

For example:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1

Approach 1: Recursive Solution

A natural approach for calculating the Fibonacci number is by employing recursion. We can directly translate the definition of the Fibonacci sequence into code.

def fib(n):
    # Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    # Recursive cases
    return fib(n-1) + fib(n-2)

This recursive solution is simple and elegant but highly inefficient. Its time complexity is exponential, O(2^n), due to the repeated calculations of the same subproblems.

Approach 2: Memoization (Top-Down Dynamic Programming)

We can optimize the recursive approach by storing the results of subproblems so that we do not recompute them. This technique is known as memoization and is a form of dynamic programming.

Here’s the Python code for this approach.

def fib(n, memo={}):
    # Check if the result is already in memo
    if n in memo:
        return memo[n]
    
    # Base cases
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        # Recursive cases with memoization
        result = fib(n-1, memo) + fib(n-2, memo)
    
    # Store the result in memo
    memo[n] = result
    
    return result

This optimized approach has a time complexity of O(n) since each subproblem is computed only once, and a space complexity of O(n) for the memoization table.

Approach 3: Tabulation (Bottom-Up Dynamic Programming)

Another form of dynamic programming involves building a table bottom-up. We can iteratively calculate Fibonacci numbers from the base cases up to the desired number.

Here’s how it’s done.

def fib(n):
    # Special case
    if n == 0:
        return 0
    
    # Initialize the table
    table = [0, 1]
    
    # Build the table bottom-up
    for i in range(2, n+1):
        table.append(table[i-1] + table[i-2])
    
    # Return the result
    return table[n]

This approach also has a time complexity of O(n) and space complexity of O(n).

Approach 4: Space-Optimized Tabulation

We can further optimize the space complexity by observing that at any iteration, we only need the last two Fibonacci numbers to calculate the next. We don’t need to store the entire sequence.

def fib(n):
    # Base cases
    if n == 0:
        return 0
    
    # Only keep the last two Fibonacci numbers
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a + b
    
    return b

This space-optimized approach has a time complexity of O(n) and a space complexity of O(1).

Conclusion

In this comprehensive article, we examined the Fibonacci Number problem on LeetCode and investigated various approaches to solve it using Python. We began with a simple recursive solution and systematically optimized it through memoization, tabulation, and space optimization.

Leave a Reply