Start learning free

LESSON 185 OF 414 · LOOPS - CHALLENGES

Fibonacci Number in Scala: 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

Guided

Ctrl + Enter to check

SCALA · LOOPS - CHALLENGES

Fibonacci in Scala, explained

Problem overview

The method fibonacci(n: Int) returns F(n), where F(0) = 0, 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.

For example, F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 and F(4) = 2 + 1 = 3. The lesson asks for O(n) time and O(1) extra space.

Approach

Translating the definition straight into a recursive method is correct but slow: each call makes two more calls, and the same values are computed over and over, so the time grows exponentially. Storing all earlier values in an array fixes the time but costs O(n) space.

The lesson's version notices that computing the next number only needs the last two. Keep those two in variables, prev and curr, and move them forward one position per pass. After the loop, curr holds F(n). That does n - 1 additions and uses a fixed number of variables.

How much work does the recursive version waste? Counting its calls gives 177 for F(10), 21,891 for F(20) and 2,692,537 for F(30). Ten more steps multiply the work by about a hundred. The loop needs 9, 19 and 29 passes for the same three inputs.

Why do two variables suffice? F(i) depends only on F(i - 1) and F(i - 2). Once F(i) is known, F(i - 2) is never needed again, so its slot can be reused. This idea of keeping only the part of the past that the next step needs comes back in many problems.

Step by step

Handle the base cases. If n < 2, return n. This covers both F(0) = 0 and F(1) = 1 with one check.
Set up the window. var prev = 0 and var curr = 1 are F(0) and F(1). They are vars because they change on every pass.
Loop from 2 to n inclusive. for (i <- 2 to n) runs once for each of F(2) through F(n). At the start of pass i, prev holds F(i - 2) and curr holds F(i - 1).
Compute the new number. val next = curr + prev is F(i). It is a val because it is set once per pass.
Slide the window. Assign prev = curr first, then curr = next. The order matters: doing it the other way round overwrites curr before its old value can be copied into prev.
Return curr. After the last pass it holds F(n).

Here is the loop for n = 5:

`i`	`prev` at start	`curr` at start	`next`	`curr` at end
2	0	1	1	1
3	1	1	2	2
4	1	2	3	3
5	2	3	5	5

The method returns 5, which is F(5).

The solution in Scala

class Solution {
    def fibonacci(n: Int): Int = {
        if (n < 2) {
            return n
        }
        var prev = 0
        var curr = 1
        for (i <- 2 to n) {
            val next = curr + prev
            prev = curr
            curr = next
        }
        return curr
    }
}

Some Scala details:

Inclusive range. 2 to n includes n. With until the loop would stop one pass early and return F(n - 1).
The loop variable is only a counter. The body never reads i; the loop just repeats the update n - 1 times. Writing for (_ <- 2 to n) says so explicitly and behaves the same.
return in the middle. The early return n is in an if, not inside a lambda, so it is an ordinary return. For the final line, curr alone would also work, because the last expression of a block is its value.
32-bit Int. The result wraps silently once it passes 2,147,483,647.

The same idea without `var`

Scala programmers often express this kind of loop with foldLeft, which carries the pair of numbers from one pass to the next instead of mutating variables:

def fib(n: Int): Int =
  if (n < 2) n
  else (2 to n).foldLeft((0, 1)) { case ((prev, curr), _) => (curr, prev + curr) }._2

The pair starts as (0, 1), each step replaces (prev, curr) with (curr, prev + curr), and ._2 picks the second item of the final pair. The underscore in the pattern ignores the range value, which is only a counter. It does the same n - 1 steps and returns the same values: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 for n from 0 to 10. The lesson uses the explicit loop because it shows the sliding window step by step.

Complexity

Time: O(n). The loop runs n - 1 times and each pass does one addition and two assignments.

Space: O(1). The method stores prev, curr, next and the loop counter, no matter how big n is.

Edge cases and common mistakes

n = 0 and n = 1. They return 0 and 1 from the base case. Without it, the loop 2 to n is empty and the method would return 1 for n = 0, which is wrong.
Overflow. F(46) is 1836311903, the largest Fibonacci number that fits in an Int. fibonacci(47) gives -1323752223 because the true value, 2971215073, wraps around. If larger inputs matter, use Long for the variables and return type.
Updating in the wrong order. Writing curr = next before prev = curr sets prev to the new number and corrupts every later value.
Off-by-one in the range. Starting the loop at 1, or ending at n - 1, gives F(n + 1) or F(n - 1).
Plain recursion. The two-call recursive version repeats work. Computing F(30) that way makes 2,692,537 calls, against 29 passes of the loop.

Testing

n = 0 gives 0 and n = 1 gives 1.
n = 2 gives 1, n = 3 gives 2, n = 4 gives 3.
n = 10 gives 55.
n = 46 gives 1836311903.

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

Start learning free