Start learning free

LESSON 181 OF 410 · LOOPS - CHALLENGES

Fibonacci in Java: O(n) Time and O(1) Space with a Loop

Practice Read the full explanation

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 and return F(n).


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.

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:


As we compute each new Fibonacci number as the sum of the previous two, we will use 2 variables prev and curr to store the last two computed Fibonacci numbers at each moment of time. We should initialize prev with 0(F(0)) and curr with 1(F(1)).

There are n - 1 more numbers to be computed: F(2), F(3), ..., F(n). Let's write a for loop that iterates with a variable i through the values 2 to n. Inside this loop, we should compute the new Fibonacci number (F(i)) and update the variables prev and curr.

At the beginning of each iteration, F(i - 2) is stored in prev, F(i - 1) is stored in curr and we want to compute F(i). At the end of the iteration, we want prev to store F(i - 1) and curr to store F(i).
So we can use another variable next to store prev + curr and then we can assign curr to prev (prev = curr) and next to curr (curr = next).

After the loop finishes execution, the answer (F(n)) lies in curr.
Also, don't forget to treat the special cases n = 0 and n = 1 (when n < 2, the answer is n itself) at the beginning of the algorithm.

STEP 1 OF 6
    Ctrl + Enter to check

    JAVA · LOOPS - CHALLENGES

    Fibonacci in Java, explained

    Problem overview

    The Fibonacci sequence starts with 0 and 1, and every later number is the sum of the two before it: F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2) for n > 1. The method fibonacci(int n) returns F(n).

    The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. So fibonacci(2) is 1 (1 + 0), fibonacci(3) is 2 (1 + 1) and fibonacci(4) is 3 (2 + 1). The lesson asks for O(n) time and O(1) extra space.

    Approach: keep only the last two numbers

    The definition translates directly into a recursive method:

    static int fibRecursive(int n) {
    return n < 2 ? n : fibRecursive(n - 1) + fibRecursive(n - 2);
}

    It is correct, but slow. fibRecursive(n) calls itself twice, and those calls repeat each other's work: F(n - 2) is computed once inside F(n - 1) and again directly. The number of calls grows exponentially, roughly 1.6 times for every step up in n, so the time is O(2^n) in the usual loose bound, and the recursion depth makes the stack use O(n). Somewhere in the 40s it already takes noticeable time, and every extra step makes it about 1.6 times slower.

    The loop version relies on one observation: to compute the next number, only the previous two are needed. Everything older can be forgotten. Two variables, prev and curr, hold the last two values, and each iteration slides that window one step forward. That computes every number exactly once, so the time is O(n), and two variables are all the memory it needs, so the space is O(1).

    Step by step

    1. Handle the base cases. If n < 2, the answer is n itself: F(0) = 0 and F(1) = 1. One check covers both.
    2. Start the window. prev = 0 is F(0) and curr = 1 is F(1). Java allows int prev = 0, curr = 1; on one line.
    3. Loop from 2 to n inclusive. These are the numbers still to compute, F(2) through F(n). At the start of the pass for index i, prev holds F(i - 2) and curr holds F(i - 1).
    4. Compute next. It is curr + prev, which is F(i).
    5. Slide the window. Copy curr into prev first, then next into curr. The order matters: reversed, the old curr would be overwritten before it could be saved, and both variables would end up holding the new value.
    6. Return curr. After the last pass it holds F(n).

    The solution in Java

    class Solution {
    public int fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        int prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            int next = curr + prev;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

    Tracing fibonacci(5): the window starts as prev = 0, curr = 1. The pass for i = 2 gives next = 1, so the window becomes (1, 1). Then i = 3 gives 2 and the window (1, 2), i = 4 gives 3 and (2, 3), and i = 5 gives 5 and (3, 5). The method returns curr, which is 5.

    The variable next is declared inside the loop, so a fresh one exists on every pass and disappears at the end of it. Only prev and curr carry information from one pass to the next.

    For inputs beyond 46, the same method with long variables works, and only the types change:

    static long fibonacciLong(int n) {
    if (n < 2) {
        return n;
    }
    long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = curr + prev;
        prev = curr;
        curr = next;
    }
    return curr;
}

    With it, fibonacciLong(47) is 2971215073 and fibonacciLong(92) is 7540113804746346429, the largest Fibonacci number that fits in a long.

    Complexity

    The loop body runs n - 1 times for n >= 2, with a fixed amount of work each, so the time is O(n). The method creates prev, curr, next and i and nothing that grows with n, so the extra space is O(1). A table of all the values (an array of size n + 1) would give the same time but O(n) space, which is why the sliding window is preferred.

    Edge cases and common mistakes

    • Integer overflow. An int holds values up to 2,147,483,647 and wraps around silently beyond that. fibonacci(46) is 1836311903, the largest Fibonacci number that fits. fibonacci(47) returns -1323752223, because the true value 2971215073 does not fit. Java gives no error for this. If larger inputs are needed, use long for the three variables, which stays correct up to F(92).
    • Missing the base cases. Without the n < 2 check, n = 0 would return 1, since the loop never runs and curr still holds its starting value.
    • Updating in the wrong order. Writing curr = next; prev = curr; sets both variables to the new number and breaks every later value.
    • Looping to n - 1 or from 1. A loop that stops one early returns F(n - 1); one that starts at 1 does one pass too many.
    • Using the naive recursion. It passes small tests and then times out, because of the repeated work described above.

    Testing

    Useful inputs: 0 returns 0, 1 returns 1, 2 returns 1, 10 returns 55 and 46 returns 1836311903. The first two check the base case, the third is the first pass of the loop, and the last sits at the edge of what an int can hold.

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free