509. Fibonacci Number

Easy

MathDynamic ProgrammingRecursionMemoization

Answered: Mar 26, 2026

Problem Description

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

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

Given n, calculate F(n).

Examples

Example 1

Input: n = 2

Output: 1

Explanation:

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

Example 2

Input: n = 3

Output: 2

Explanation:

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

Example 3

Input: n = 4

Output: 3

Explanation:

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

Constraints

0 <= n <= 30

Solutions

Complexity Analysis

Time Complexity:

O (n)

We perform a single loop from 2 to n, executing a constant amount of work per iteration.

Space Complexity:

O (1)

Only two variables (f0 and f1) are used regardless of input size.

This approach iteratively builds up the Fibonacci sequence by keeping track of only the last two values at each step. We initialize f0 = 0 and f1 = 1 for the base cases, then loop from 2 to n, advancing the window forward by saving f1 into a temporary variable, computing the new f1 as the sum of the previous two, and shifting f0 up. After the loop, f1 holds F(n).

Complexity Analysis

Time Complexity:

O (n)

We loop from 2 to n once, doing $O(1)$ work per step.

Space Complexity:

O (1)

Only two variables are maintained at any time, with no dependency on input size.

This is the same iterative approach as Solution 1, but uses simultaneous assignment (a, b = b, a + b) to advance the two pointers in a single line, eliminating the need for a temporary variable. Starting from a = 0, b = 1, each iteration shifts a to the previous b and b to their sum, so after n - 1 iterations b holds F(n).

Complexity Analysis

Time Complexity:

O (n)

Each unique value from 2 to n is computed exactly once and cached, so there are $O(n)$ total recursive calls.

Space Complexity:

O (n)

The memo dictionary stores up to n entries, and the recursion call stack reaches a depth of n.

This approach uses top-down dynamic programming: a recursive helper fib_helper computes F(n) by breaking it into F(n-1) + F(n-2), but stores each result in a memo dictionary before returning so that any subproblem is only solved once. On subsequent calls with the same n, the cached value is returned immediately, avoiding the exponential blowup of naive recursion.

Complexity Analysis

Time Complexity:

O (n)

The loop runs from index 2 to n, performing $O(1)$ work at each step.

Space Complexity:

O (n)

The dp array stores n + 1 values.

This approach uses bottom-up dynamic programming by allocating an array dp of size n + 1, seeding dp[0] = 0 and dp[1] = 1, then filling each entry from index 2 to n using the recurrence dp[i] = dp[i-1] + dp[i-2]. The answer is simply dp[n] after the loop completes.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Iterative with Temporary Variable	$O(n)$	$O(1)$	$O(1)$ space, easy to understand the swap logic explicitly	Requires a temporary variable; more verbose than necessary
Iterative - Pythonic Swap	$O(n)$	$O(1)$	Cleanest and most concise; optimal time and space	Simultaneous assignment may be less intuitive in non-Python languages
Top-Down DP (Memoization)	$O(n)$	$O(n)$	Natural recursive structure mirrors the problem definition	$O(n)$ extra space for memo dict and call stack; recursion overhead
Bottom-Up DP	$O(n)$	$O(n)$	Avoids recursion; straightforward DP table approach	Stores all n+1 values unnecessarily when only last two are needed

The optimal approach for this problem is Solution 2: Iterative - Pythonic Swap, which achieves $O(n)$ time complexity and $O(1)$ space complexity. It delivers the same optimal performance as Solution 1 but in a single, elegant line using simultaneous assignment, making it the most concise and idiomatic implementation.

Solutions

lines
1class Solution:
  def fib(self, n: int) -> int:
      # Base cases
      if n <= 1:
          return n
6
      # Iteratively compute Fibonacci numbers up to n
      f0, f1 = 0, 1
9
      # Loop from 2 to n, updating f0 and f1 to hold the last two Fibonacci numbers
      for _ in range(2, n + 1):
          temp = f1
          f1 = f1 + f0  # F(n) = F(n-1) + F(n-2)
          f0 = temp  # Update f0 to the previous Fibonacci number (F(n-1))
15
      # After the loop, f1 holds the value of F(n)
      return f1

Complexity Analysis

Time Complexity:

O (n)

We perform a single loop from 2 to n, executing a constant amount of work per iteration.

Space Complexity:

O (1)

Only two variables (f0 and f1) are used regardless of input size.

lines
1class Solution:
  def fib(self, n: int) -> int:
      # Base cases
      if n <= 1:
          return n
6
      # Iteratively compute Fibonacci numbers up to n
      a, b = 0, 1
9
      # Loop from 2 to n, updating a and b to hold the last two Fibonacci numbers
      for _ in range(2, n + 1):
          a, b = b, a + b
13
      # After the loop, b holds the value of F(n)
      return b

Complexity Analysis

Time Complexity:

O (n)

We loop from 2 to n once, doing $O(1)$ work per step.

Space Complexity:

O (1)

Only two variables are maintained at any time, with no dependency on input size.

lines
1class Solution:
  def fib(self, n: int) -> int:
      # Base cases
      if n <= 1:
          return n
6
      # Create a memoization dictionary to store previously computed Fibonacci numbers
      memo = {}
9
      def fib_helper(n):
          # Check if the value is already computed
          if n in memo:
              return memo[n]
14
          # Compute the Fibonacci number recursively and store it in the memo dictionary
          memo[n] = fib_helper(n - 1) + fib_helper(n - 2)
17
          return memo[n]
19
      # Call the helper function to compute the Fibonacci number for n
      return fib_helper(n)

Complexity Analysis

Time Complexity:

O (n)

Each unique value from 2 to n is computed exactly once and cached, so there are $O(n)$ total recursive calls.

Space Complexity:

O (n)

The memo dictionary stores up to n entries, and the recursion call stack reaches a depth of n.

lines
1class Solution:
  def fib(self, n: int) -> int:
      # Base cases
      if n <= 1:
          return n
6
      # Create a dp array to store Fibonacci numbers up to n
      dp = [0] * (n + 1)
      dp[1] = 1
10
      # Iteratively compute Fibonacci numbers up to n
      for i in range(2, n + 1):
          # The Fibonacci number at index i is the sum of the two preceding numbers
          dp[i] = dp[i - 1] + dp[i - 2]
15
      # After the loop, dp[n] holds the value of F(n)
      return dp[n]

Complexity Analysis

Time Complexity:

O (n)

The loop runs from index 2 to n, performing $O(1)$ work at each step.

Space Complexity:

O (n)

The dp array stores n + 1 values.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Iterative with Temporary Variable	$O(n)$	$O(1)$	$O(1)$ space, easy to understand the swap logic explicitly	Requires a temporary variable; more verbose than necessary
Iterative - Pythonic Swap	$O(n)$	$O(1)$	Cleanest and most concise; optimal time and space	Simultaneous assignment may be less intuitive in non-Python languages
Top-Down DP (Memoization)	$O(n)$	$O(n)$	Natural recursive structure mirrors the problem definition	$O(n)$ extra space for memo dict and call stack; recursion overhead
Bottom-Up DP	$O(n)$	$O(n)$	Avoids recursion; straightforward DP table approach	Stores all n+1 values unnecessarily when only last two are needed

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Solutions

Solution 1: Iterative with Temporary Variable

Complexity Analysis

Explanation

Solution 2: Iterative - Pythonic Swap

Complexity Analysis

Explanation

Solution 3: Top-Down DP (Memoization)

Complexity Analysis

Explanation

Solution 4: Bottom-Up DP

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Solutions

Solution 1: Iterative with Temporary Variable

Complexity Analysis

Explanation

Solution 2: Iterative - Pythonic Swap

Complexity Analysis

Explanation

Solution 3: Top-Down DP (Memoization)

Complexity Analysis

Explanation

Solution 4: Bottom-Up DP

Complexity Analysis

Explanation

Conclusion