Start learning free

LESSON 186 OF 415 · LOOPS - CHALLENGES

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

    SWIFT · LOOPS - CHALLENGES

    Fibonacci in Swift, explained

    Problem overview

    The method fibonacci(_ n: Int) returns F(n), the n-th Fibonacci number. The sequence starts with 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.

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

    Approach

    The definition suggests recursion: F(n) calls F(n - 1) and F(n - 2). That works, but it recomputes the same values again and again, and its running time grows exponentially. A loop avoids this. To get the next number you only need the last two, so keep just those two values, produce the next one, and slide forward by one position. After n - 1 steps beyond the starting pair, you hold F(n). Two variables are all the memory required, which is the O(1) space the statement asks for.

    Step by step

    1. Handle the base cases first. If n < 2, return n. Since F(0) = 0 and F(1) = 1, the answer equals the input, and one check covers both.
    2. Declare the two running values in one var declaration: prev = 0 and curr = 1, the values of F(0) and F(1). At the start of an iteration for index i, prev holds F(i - 2) and curr holds F(i - 1).
    3. Loop from 2 through n with the closed range 2...n, so that F(2) to F(n) are all computed.
    4. Compute the new number as a constant: let next = curr + prev. This is F(i).
    5. Slide the window. Assign prev = curr first, then curr = next. The order matters: the other way round would overwrite curr before it is saved. With prev = 1 and curr = 2, the update gives prev = 2 and curr = 3.
    6. Return curr. After the loop it holds F(n).

    The solution in Swift

    class Solution {
    func fibonacci(_ n: Int) -> Int {
        if n < 2 {
            return n
        }
        var prev = 0, curr = 1
        for i in 2...n {
            let next = curr + prev
            prev = curr
            curr = next
        }
        return curr
    }
}

    Swift details worth knowing:

    • The base case protects the range. 2...n is a closed range, and Swift requires its lower bound to be at most its upper bound. A call like 2...1 stops the program at run time. Because the method returns early for n < 2, the loop always has n >= 2.
    • The unused loop variable. i is only there to count iterations. Swift compiles this with a warning that it is never used; writing for _ in 2...n avoids the warning and works the same way.
    • Several variables in one declaration. var prev = 0, curr = 1 declares both as Int variables.
    • Swift can swap in one statement, using a tuple: (prev, curr) = (curr, prev + curr). It does the same job as the three lines in the loop body.
    • Overflow traps. Int is 64 bits. F(92) is 7540113804746346429 and fits, but F(93) does not: computing it stops the program with a run-time error instead of wrapping around quietly. The wrapping operator &+ would make it wrap, but then the values stop being Fibonacci numbers.

    Tracing the loop

    For n = 6, the loop starts with prev = 0 and curr = 1. Each pass produces the next number and moves the pair forward:

    • i = 2: next = 1, so the pair becomes (1, 1).
    • i = 3: next = 2, so the pair becomes (1, 2).
    • i = 4: next = 3, so the pair becomes (2, 3).
    • i = 5: next = 5, so the pair becomes (3, 5).
    • i = 6: next = 8, so the pair becomes (5, 8).

    The loop ends and the method returns curr, which is 8, the value of F(6). The pair always holds two consecutive Fibonacci numbers, and that invariant is the whole idea of the solution.

    Why not recursion

    A direct translation of the definition looks like this:

    var calls = 0
func fibRec(_ n: Int) -> Int {
    calls += 1
    if n < 2 { return n }
    return fibRec(n - 1) + fibRec(n - 2)
}

    Counting the calls shows the problem:

    nF(n)Calls
    5515
    1055177
    20676521,891
    308320402,692,537

    Each increase of 10 in n multiplies the calls by more than a hundred, because fibRec(n - 1) and fibRec(n - 2) each repeat most of the other's work. The loop computes every F(i) exactly once, which is why the lesson uses it.

    Complexity

    Time: O(n). The loop runs n - 1 times and each pass does an addition and two assignments. Space: O(1). The method uses prev, curr, next and the loop variable, whatever the value of n. The recursive definition, in contrast, makes an exponential number of calls.

    Reading the result type

    The method returns Int, so the answer is an exact integer and not a floating-point approximation. Unlike a language that silently switches to big numbers, Swift's fixed-width Int keeps arithmetic fast but limits this method to n up to 92. Tests with larger n would need a different representation, which is outside this lesson.

    Edge cases and common mistakes

    • n = 0 and n = 1. The early return gives 0 and 1. Without it, 2...0 would crash the program.
    • n = 2. The loop runs once: next = 1 + 0 = 1, and curr becomes 1. The answer is 1.
    • Updating in the wrong order. Setting curr = next before prev = curr makes prev equal to the new value, and the sequence goes wrong.
    • Returning next. It is declared inside the loop body, so it isn't visible after the loop; curr carries the result out.
    • Using 2..<n. The half-open range stops one step early and returns F(n - 1).

    Testing

    • n = 0 gives 0, n = 1 gives 1.
    • n = 2 gives 1, n = 3 gives 2, n = 4 gives 3.
    • n = 10 gives 55.
    • n = 50 gives 12586269025.
    • n = 92 gives 7540113804746346429.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free