Nth Fibonacci

Tags

Nth Fibonacci

Category

Recursion

Difficulty

Easy

Problem Statement

Given a positive integer n, return the nth Fibonacci number. The Fibonacci sequence is defined as: F(1) = 0, F(2) = 1, and F(n) = F(n-1) + F(n-2) for n > 2.

Intuition

The Fibonacci sequence is a classic example of overlapping subproblems. Each number is simply the sum of the two preceding numbers. While a naive recursive solution recomputes the same values many times, we can optimize by storing previously computed results (memoization) or by iterating from the bottom up, only tracking the last two values.

Approach

  1. Initialize two variables representing the two most recent Fibonacci numbers: prev = 0 and curr = 1.
  2. Iterate from 3 to n (since we already know F(1) and F(2)).
  3. On each iteration, compute the next value as prev + curr, then shift the window forward: prev becomes the old curr, and curr becomes the newly computed value.
  4. Return curr after the loop completes (or prev if n == 1).

Pseudocode

function nthFib(n):
    if n == 1: return 0
    if n == 2: return 1

    prev = 0
    curr = 1
    for i from 3 to n:
        next = prev + curr
        prev = curr
        curr = next
    return curr

Time & Space Complexity

  • Time: O(n) — we iterate through the sequence once.
  • Space: O(1) — we only store two variables regardless of input size.

Note: A naive recursive solution would be O(2^n) time and O(n) space (call stack). A memoized recursive solution would be O(n) time and O(n) space.

Key Insights

  • The iterative approach is optimal because we only ever need the last two values.
  • Memoization converts the exponential recursive solution into a linear one by caching results.
  • The problem is a foundational example of dynamic programming — solving larger problems from smaller subproblem solutions.

Edge Cases

  • n = 1 should return 0 (the first Fibonacci number).
  • n = 2 should return 1.
  • Verify the indexing convention: some definitions start with F(0) = 0, others with F(1) = 0. Clarify with the problem statement.
  • Very large n values may cause integer overflow in some languages.

Linked mentions