Linear time Nth Fibonacci number

You're in a LinkedIn phone screen and the interviewer asks, "Can you compute the Nth Fibonacci number efficiently?" It sounds simple - most candidates have seen Fibonacci before. But the follow-up is what separates a passing answer from a strong one: "Now do it in O(n) time and O(1) space." This problem, also known as "Fibonacci Number" on other platforms, tests whether you can move beyond the textbook recursive definition and think about performance.

TL;DR

Compute the Nth Fibonacci number iteratively by maintaining two variables that track F(n-1) and F(n-2). At each step, compute the current Fibonacci number as their sum, then slide both variables forward. Handle base cases directly: F(0) = 0, F(1) = 1, F(2) = 1. This runs in O(n) time and O(1) space, compared to naive recursion's O(2^n) time and O(n) stack space.

Why This Problem Matters

Fibonacci is the gateway to understanding dynamic programming. The jump from a recursive solution to an iterative one with constant space captures the same optimization pattern you'll use on dozens of harder DP problems: identify the recurrence, recognize how many previous states you actually need, and compress the table. Companies like LinkedIn use it as a warm-up, but the underlying technique shows up in problems involving path counting, stock trading, and string manipulation.

The Fibonacci Sequence

The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

The recurrence relation is straightforward:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n ≥ 2

This definition is recursive by nature, which makes the naive recursive solution tempting. But there's a serious performance problem hiding in that recursion.

Understanding the Problem

Given: A non-negative integer n (where 0 ≤ n ≤ 90) Return: The nth Fibonacci number Constraints: Must run in O(n) time and O(1) space

betterFibonacci(0) -> 0
betterFibonacci(1) -> 1
betterFibonacci(3) -> 2

The constraint on n being at most 90 is deliberate. Fibonacci numbers grow exponentially, and F(90) = 2,880,067,194,370,816,120, which fits in a 64-bit long. Going beyond that risks integer overflow.

Why Recursion Falls Short

The naive recursive implementation directly translates the mathematical definition:

long fibonacci(int n) {
    if (n == 0) return 0;
    if (n <= 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This creates an explosion of redundant calls. Computing F(5) alone generates this call tree:

Notice that F(3) is computed twice, F(2) is computed three times. For F(40), the number of function calls exceeds a billion. The time complexity is O(2^n), which is completely impractical for large inputs.

Solution Approach

The fix is to compute Fibonacci numbers from the bottom up instead of top down. Since each value only depends on the previous two, we don't need an array of all values. Two variables are enough.

Think of it as a window sliding along the sequence:

At each step, nMinus2 and nMinus1 hold the two most recent Fibonacci numbers. We compute the next one, then shift the window forward by one position. The old nMinus1 becomes the new nMinus2, and the result becomes the new nMinus1.

Building the Algorithm

1. Handle base cases: return 0 for n = 0, return 1 for n = 1 or n = 2
2. Initialize nMinus2 = 1 (representing F(1)) and nMinus1 = 1 (representing F(2))
3. Loop from i = 3 to n, computing result = nMinus1 + nMinus2 at each step
4. After computing the result, slide the window: nMinus2 = nMinus1, then nMinus1 = result
5. Return the final result

Here's how the variables evolve when computing F(6):

Each iteration does constant work: one addition and two assignments. After 4 iterations (from i = 3 to i = 6), result holds F(6) = 8.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public long betterFibonacci(int n) {
    // Handle base cases: F(0) = 0, F(1) = F(2) = 1
    if (n == 0) return 0;
    if (n <= 2) return 1;

    // Initialize sliding window at F(1) and F(2)
    long nMinus1 = 1, nMinus2 = 1, result = 0;

    // Compute F(3) through F(n) iteratively
    for (int i = 3; i <= n; i++) {
      // Current Fibonacci number is sum of previous two
      result = nMinus1 + nMinus2;
      // Slide the window forward
      nMinus2 = nMinus1;
      nMinus1 = result;
    }

    return result;
  }
}

The variable naming makes the algorithm self-documenting. At any point in the loop, nMinus1 holds F(i-1) and nMinus2 holds F(i-2), so result = nMinus1 + nMinus2 directly implements the recurrence relation.

Complexity Analysis

Time Complexity: O(n)

The loop runs from 3 to n, performing a constant amount of work per iteration (one addition, two assignments). For inputs where n ≤ 2, the function returns immediately. Total operations scale linearly with n.

Space Complexity: O(1)

Only three scalar variables (nMinus1, nMinus2, result) are allocated regardless of the input size. There is no array, no hash map, and no recursion stack. This is the optimal space usage for this problem.

Comparison with Other Approaches

The iterative approach hits the sweet spot between simplicity and performance. Matrix exponentiation is faster in theory, but interviewers almost never expect it, and the constant factors make it slower than the iterative version for typical interview inputs (n ≤ 90).

Common Pitfalls

1. Forgetting F(0) as a special case. F(0) = 0, not 1. If you only check n <= 2, you'll return 1 for n = 0.

2. Using int instead of long. F(46) already exceeds the 32-bit integer maximum (2,147,483,647). The problem allows n up to 90, so you need a 64-bit type.

3. Updating variables in the wrong order. If you write nMinus1 = result before nMinus2 = nMinus1, you've overwritten nMinus1 and lost the value that nMinus2 needs. Always update nMinus2 first.

4. Starting the loop at the wrong index. The loop should start at 3, not 0 or 1. Starting at 1 computes too many iterations, producing the wrong result.

Interview Tips

When this problem comes up:

1. Acknowledge the recursive definition and immediately explain why it's inefficient. This shows you understand the tradeoff without needing to be prompted.

2. Mention the DP connection. "This is bottom-up DP with space optimization, since we only need the last two values." Interviewers like hearing you connect the dots.

3. Watch your types. Mention that you're using long because Fibonacci numbers grow exponentially. This demonstrates awareness of overflow, which is a real-world concern.

4. If asked about follow-ups, mention matrix exponentiation for O(log n) time, or Binet's formula (the closed-form using the golden ratio, which has precision issues for large n).

5. Trace through a small example on the whiteboard. Pick n = 5 or n = 6 and walk through the loop iterations. It takes 30 seconds and makes your solution concrete.

Key Takeaways

• The iterative sliding window computes F(n) in O(n) time and O(1) space by keeping only the two most recent values, making it the optimal approach for interviews.
• Handle three base cases explicitly: F(0) = 0, F(1) = 1, F(2) = 1. Missing the F(0) case is the most common bug.
• Use a 64-bit integer type (long in Java/C++, int64 in Go) because Fibonacci numbers overflow 32-bit integers at F(46).
• Update nMinus2 before nMinus1 in each iteration. Reversing the order silently corrupts the computation.
• This problem is a distilled example of bottom-up DP with space optimization, a pattern that transfers directly to problems like climbing stairs, house robber, and minimum cost paths.

Practice and Related Problems

Once you're comfortable with this iterative pattern, apply the same technique to these related problems:

• Nth Fibonacci number with recursion (compare the two approaches side by side)
• Step Combinations to Reach the Summit (climbing stairs is Fibonacci in disguise)
• Street Safe Heist Strategy (house robber uses the same two-variable window)
• Simple Recursive Raise to Power (another recursion-to-iteration conversion)

This problem and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. The spaced repetition system ensures you don't just solve a problem once but retain the pattern long-term.

Solutions in Other Languages

Python

class Solution:
    def better_fibonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1

        n_minus_1, n_minus_2 = 1, 1
        result = 0

        for i in range(3, n + 1):
            result = n_minus_1 + n_minus_2
            n_minus_2 = n_minus_1
            n_minus_1 = result

        return result

JavaScript

class Solution {
  betterFibonacci(n) {
    if (n === 0) return 0;
    if (n <= 2) return 1;

    let nMinus1 = 1, nMinus2 = 1, result = 0;

    for (let i = 3; i <= n; i++) {
      result = nMinus1 + nMinus2;
      nMinus2 = nMinus1;
      nMinus1 = result;
    }

    return result;
  }
}

Note: JavaScript uses 64-bit floating point numbers, which can represent integers exactly up to 2^53 - 1. For very large Fibonacci numbers, consider using BigInt.

TypeScript

class Solution {
  betterFibonacci(n: number): number {
    if (n === 0) return 0;
    if (n <= 2) return 1;

    let nMinus1 = 1, nMinus2 = 1, result = 0;

    for (let i = 3; i <= n; i++) {
      result = nMinus1 + nMinus2;
      nMinus2 = nMinus1;
      nMinus1 = result;
    }

    return result;
  }
}

C++

#include <iostream>

class Solution {
public:
  long betterFibonacci(int n) {
    if (n == 0) return 0;
    if (n <= 2) return 1;

    long nMinus1 = 1, nMinus2 = 1, result = 0;

    for (int i = 3; i <= n; i++) {
      result = nMinus1 + nMinus2;
      nMinus2 = nMinus1;
      nMinus1 = result;
    }

    return result;
  }
};

Go

package solution

func (s *Solution) BetterFibonacci(n int) int64 {
    if n == 0 {
        return 0
    }
    if n <= 2 {
        return 1
    }

    nMinus1, nMinus2 := int64(1), int64(1)
    var result int64

    for i := 3; i <= n; i++ {
        result = nMinus1 + nMinus2
        nMinus2 = nMinus1
        nMinus1 = result
    }

    return result
}

Scala

class Solution {
  def betterFibonacci(n: Int): Long = {
    if (n == 0) return 0L
    if (n <= 2) return 1L

    var nMinus1: Long = 1L
    var nMinus2: Long = 1L
    var result: Long = 0L

    for (_ <- 3 to n) {
      result = nMinus1 + nMinus2
      nMinus2 = nMinus1
      nMinus1 = result
    }

    result
  }
}

Kotlin

class Solution {
    fun betterFibonacci(n: Int): Long {
        if (n == 0) return 0
        if (n <= 2) return 1

        var nMinus1 = 1L
        var nMinus2 = 1L
        var result = 0L

        for (i in 3..n) {
            result = nMinus1 + nMinus2
            nMinus2 = nMinus1
            nMinus1 = result
        }

        return result
    }
}

Ruby

class Solution
  def better_fibonacci(n)
    return 0 if n == 0
    return 1 if n <= 2

    n_minus_1 = 1
    n_minus_2 = 1
    result = 0

    (3..n).each do |i|
      result = n_minus_1 + n_minus_2
      n_minus_2 = n_minus_1
      n_minus_1 = result
    end

    result
  end
end

Swift

class Solution {
    func betterFibonacci(_ n: Int) -> Int64 {
        if n == 0 { return 0 }
        if n <= 2 { return 1 }

        var nMinus1: Int64 = 1
        var nMinus2: Int64 = 1
        var result: Int64 = 0

        for _ in 3...n {
            result = nMinus1 + nMinus2
            nMinus2 = nMinus1
            nMinus1 = result
        }

        return result
    }
}

C#

public class Solution {
    public long betterFibonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;

        long nMinus1 = 1, nMinus2 = 1, result = 0;

        for (int i = 3; i <= n; i++) {
            result = nMinus1 + nMinus2;
            nMinus2 = nMinus1;
            nMinus1 = result;
        }

        return result;
    }
}

PHP

class Solution {
    public function betterFibonacci(int $n): int {
        if ($n == 0) return 0;
        if ($n <= 2) return 1;

        $nMinus1 = 1;
        $nMinus2 = 1;
        $result = 0;

        for ($i = 3; $i <= $n; $i++) {
            $result = $nMinus1 + $nMinus2;
            $nMinus2 = $nMinus1;
            $nMinus1 = $result;
        }

        return $result;
    }
}