LESSON 166 OF 338 · LOOPS - CHALLENGES

Fibonacci Number in Go: O(n) Time and O(1) Space

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 shoud 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 = 1 and n = 2 at the beginning of the algorithm.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Fibonacci in Go, explained

Problem overview

The function fibonacci receives an integer n and returns F(n), the n-th Fibonacci number. The sequence starts F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n - 1) + F(n - 2).

The sequence begins 0, 1, 1, 2, 3, 5, 8, 13. So F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 and F(4) = 2 + 1 = 3. The task asks for O(n) time and O(1) extra space.

Approach: keep only the last two numbers

The definition looks like a recursive function, but a direct recursion calls itself twice per level and recomputes the same values again and again. Its running time grows exponentially.

The loop version works because each new number needs only the previous two. Instead of storing the whole sequence, keep two variables, prev and curr, holding F(i - 2) and F(i - 1). On each pass, compute F(i) from them, then slide the window one step: the old curr becomes prev and the new number becomes curr. That is n - 1 passes (for F(2) up to F(n)) and two variables of memory.

Take n = 4. Start with prev = 0, curr = 1. At i = 2, the new value is 1, and the pair becomes (1, 1). At i = 3 it is 2, and the pair becomes (1, 2). At i = 4 it is 3, and the pair becomes (2, 3). The answer is curr, which is 3.

Step by step

Handle the base cases. If n is less than 2, return n. That covers both F(0) = 0 and F(1) = 1 with a single check.
Set the starting pair. Declare prev and curr together with :=, as 0 and 1, the values of F(0) and F(1).
Loop from 2 to n. Declare i in the for header, starting at 2 and running while it is at most n, so every number from F(2) through F(n) is computed.
Compute the new number. Declare next as curr + prev.
Slide the window. Assign curr to prev first, then next to curr. This order matters: if curr were overwritten first, its old value would be lost before prev could take it.
Return curr. After the last pass it holds F(n).

The solution in Go

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

Go details to notice:

Multiple assignment. prev, curr := 0, 1 declares two variables in one statement. Go also lets you update a pair at once with prev, curr = curr, prev + curr, because the right side is fully evaluated before any assignment. That would replace the three lines in the loop. The lesson uses a named next to show each step.
Early return. The if with a return handles the special cases up front, so the rest of the function can assume n >= 2. Go style prefers this to an else block.
next is not a keyword. Go has no next keyword, so the name is fine. A variable named next is local to the loop body.
Unused variables don't compile. Declaring next and not using it would be a compile error. Here it is used twice.
Overflow. An int is 64 bits, and overflow wraps silently. fibonacci(92) is 7540113804746346429, which fits. fibonacci(93) returns a negative number, -6246583658587674878, because the true value is larger than the biggest int.

Complexity

Time: O(n). The loop runs n - 1 times with constant work per pass.

Space: O(1). The variables prev, curr, next and i use the same memory whatever the size of n. Keeping all the numbers in a slice would work too, but it would cost O(n) space.

Edge cases and common mistakes

n = 0 and n = 1. Without the early return, the loop would not run, and the function would return curr, which is 1. That is right for n = 1 and wrong for n = 0, which should give 0.
n = 2. The loop runs once and gives 1.
Wrong order of updates. Setting curr = next before prev = curr makes both variables equal the new number, so the sequence stops growing correctly.
Looping to n - 1. An off-by-one error here returns F(n - 1). The comparison must be i <= n.
Naive recursion. The two-call recursive version is correct but takes exponential time, so it becomes unusable for n around 50.

Testing

n = 0 gives 0.
n = 1 gives 1.
n = 4 gives 3.
n = 10 gives 55.
n = 50 gives 12586269025.

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

Start learning free