LESSON 187 OF 415 · LOOPS - CHALLENGES

Tribonacci in Swift: O(n) Time and O(1) Space with a Loop

The Tribonacci numbers, commonly denoted T(n) form a sequence, called the Tribonacci sequence, such that each number is the sum of the three preceding ones, starting from 0, 1 and 1. That is,

T(0) = 0, T(1) = 1, T(2) = 1
T(n) = T(n - 1) + T(n - 2) + T(n - 3), for n > 2.

Given n, calculate and return T(n).

Example 1:

Input: n = 3
Output: 2
Explanation: T(3) = T(2) + T(1) + T(0) = 1 + 1 + 0 = 2.

Example 2:

Input: n = 4
Output: 4
Explanation: T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4.

Example 3:

Input: n = 5
Output: 7
Explanation: T(5) = T(4) + T(3) + T(2) = 4 + 2 + 1 = 7.

Note:

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

STEP 1 OF 8

Guided

Ctrl + Enter to check

SWIFT · LOOPS - CHALLENGES

Tribonacci in Swift, explained

Problem overview

The method tribonacci(_ n: Int) -> Int returns the n-th Tribonacci number. The sequence starts T(0) = 0, T(1) = 1, T(2) = 1, and from then on each number is the sum of the three before it: T(n) = T(n - 1) + T(n - 2) + T(n - 3).

For n = 4 the answer is 4, because T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1. For n = 5 it is 7. The lesson asks for O(n) time and O(1) extra space.

Approach: keep only the last three values

The definition suggests recursion, but a plain recursive function calls itself three times per level and recomputes the same values again and again, so its running time grows exponentially. Storing every value in an array fixes the time but uses O(n) space.

Each new number needs only the three before it. So three variables are enough: the newest value and the two behind it. On every iteration you compute the next number, then slide the window one step forward. That is one pass with a fixed amount of memory.

Here is the window for n = 5, written as (prev2, prev, curr):

start:        (0, 1, 1)   curr is T(2)
i = 3:        (1, 1, 2)   curr is T(3)
i = 4:        (1, 2, 4)   curr is T(4)
i = 5:        (2, 4, 7)   curr is T(5)

Why is the shift order safe? After next is computed, the old prev2 is no longer needed, because the next number depends only on prev, curr and next. So prev2 can be overwritten first, then prev, then curr, and at each assignment the value being copied has not been touched yet. Swift could also do the three assignments at once with a tuple, (prev2, prev, curr) = (prev, curr, next), but the lesson spells out each one so the order is visible.

Compare the three ways to solve this. Plain recursion is the shortest to write but takes exponential time. Memoization, which stores each result in an array or dictionary, takes O(n) time and O(n) space. The rolling window takes O(n) time and O(1) space, which is what the lesson's note asks for. It is the same idea as an iterative Fibonacci, with a window of three values instead of two.

Step by step

Handle 0 and 1 first. For n < 2 the answer is n itself, so return it right away.
Declare the window. prev2, prev and curr start as T(0), T(1) and T(2). They are var because they change on every iteration.
Loop from 3 up to n. Each pass produces one more Tribonacci number. The counter is never used, so it is named _.
Compute next as the sum of the three values. It is a let because it is created fresh in every pass.
Shift the window, oldest first. Copy prev into prev2, then curr into prev, then next into curr. Each variable is overwritten only after its old value has been copied one place back.
Return curr after the loop. It holds T(n).

The solution in Swift

class Solution {
    func tribonacci(_ n: Int) -> Int {
        if n < 2 {
            return n
        }
        var prev2 = 0, prev = 1, curr = 1
        for _ in stride(from: 3, through: n, by: 1) {
            let next = prev2 + prev + curr
            prev2 = prev
            prev = curr
            curr = next
        }
        return curr
    }
}

The Swift details worth a closer look:

Several variables in one var. var prev2 = 0, prev = 1, curr = 1 declares three Int variables in one statement. Swift infers each type from its value.
stride instead of 3...n. stride(from: 3, through: n, by: 1) includes n, like a closed range. The difference shows when n is 2: the stride is simply empty, so curr (which is T(2)) is returned. The range 3...n would stop the program, because Swift cannot build a range whose end is below its start. to: in place of through: would leave n out.
The loop variable _. It tells Swift, and the reader, that the counter is not needed.
Parameters are constants. The method never assigns to n, which is why it needs no mutable copy. Only the three window variables change.

One more point about the early return. Without it, n = 0 and n = 1 would fall through to the loop setup, which assumes T(2) exists, and return 1 for both. The guard covers those two cases, and also returns n for a negative input, which the lesson never tests.

Complexity

Time: O(n). The loop runs n - 2 times for n >= 3, and each pass does a fixed amount of work.

Space: O(1). The method uses four integers (prev2, prev, curr and next), no matter how large n is.

Edge cases and common mistakes

n = 0, 1 and 2. 0 and 1 return through the early if. For 2 the loop does not run and curr, which is 1, comes back.
Shifting in the wrong order. If curr = next comes before prev = curr, the old curr is lost and prev receives the new value, so every later number is wrong.
Returning next. next exists only inside the loop, and it would be missing when the loop does not run. Return curr.
Overflow. An Int has 64 bits. T(73) is 7015254043203144209 and still fits, but T(74) does not. Swift does not wrap on overflow: the addition stops the program with a run-time error. Wrapping operators such as &+ would avoid the crash but return a wrong, negative number, so they are not the fix here.

Testing

n = 0 gives 0.
n = 2 gives 1.
n = 3 gives 2.
n = 4 gives 4.
n = 5 gives 7.
n = 10 gives 149.
n = 37 gives 2082876103.

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

Start learning free