Start learning free

LESSON 166 OF 348 · LOOPS - CHALLENGES

Fibonacci Number in TypeScript: O(n) Time, O(1) Space

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 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
    Ctrl + Enter to check

    TYPESCRIPT · LOOPS - CHALLENGES

    Fibonacci in TypeScript, explained

    Problem overview

    The method fibonacci(n) returns F(n), the n-th Fibonacci number. The sequence starts F(0) = 0, F(1) = 1, and from then on each number is the sum of the two before it: F(n) = F(n - 1) + F(n - 2). The first values are 0, 1, 1, 2, 3, 5, 8, 13.

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

    Approach: keep only the last two numbers

    The definition suggests recursion: to get F(n), compute F(n - 1) and F(n - 2). Written directly, that recalculates the same values over and over, and the number of calls grows exponentially. The sequence also gives a much simpler path. Each value depends only on the two before it, so there is no reason to store the whole sequence or to start from n and go down.

    Start from the bottom instead. Keep two variables, prev and curr, holding F(0) and F(1). Then repeat the same step n - 1 times: compute the next number as curr + prev, and slide the window forward so that prev takes the old curr and curr takes the new number. When the loop ends, curr is F(n).

    Why the direct recursion is too slow

    Here is the definition written as a recursive function:

    function fibRec(n: number): number {
  if (n < 2) return n;
  return fibRec(n - 1) + fibRec(n - 2);
}

    It is correct, but fibRec(5) calls fibRec(3) twice, fibRec(2) three times, and so on. Counting the calls shows what happens: 177 calls for n = 10, 21,891 for n = 20 and 2,692,537 for n = 30. Each step up in n multiplies the work by roughly 1.6. The loop avoids all of it by computing each value once, from the bottom, and keeping only what the next step needs. This idea of building up from small cases is the core of dynamic programming.

    Why not store the whole sequence?

    A common first attempt fills an array: fib[0] = 0, fib[1] = 1, then fib[i] = fib[i - 1] + fib[i - 2] for each i up to n, and returns fib[n]. It runs in O(n) time as well and is easy to follow, but it keeps n + 1 numbers when only two are ever read again. The statement asks for O(1) space, so the two-variable window is the version to write here. Recognising that a result depends on a fixed number of recent values, and keeping only those, is a pattern you will meet again.

    Step by step

    1. Handle the base cases. If n < 2, return n: F(0) is 0 and F(1) is 1, so the input is its own answer. This also covers both starting values with one check.
    2. Declare prev and curr as 0 and 1. At the start of each iteration for i, prev holds F(i - 2) and curr holds F(i - 1).
    3. Loop with i from 2 to n, inclusive, because F(2) through F(n) are the values still to compute.
    4. Compute next as curr + prev. This is F(i).
    5. Slide the window. Assign curr to prev first, then next to curr. The order matters: reversing it would overwrite curr before its old value was saved. Check with prev = 1 and curr = 2: afterwards prev = 2 and curr = 3.
    6. Return curr after the loop.

    Take n = 4. The state starts as prev = 0, curr = 1. At i = 2, next = 1, so the state becomes prev = 1, curr = 1. At i = 3, next = 2 and the state becomes prev = 1, curr = 2. At i = 4, next = 3 and the state becomes prev = 2, curr = 3. The method returns 3.

    The solution in TypeScript

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

    One let declares both prev and curr, separated by a comma. The compiler infers their type as number from the initial values, so no annotation is needed. next is declared inside the loop body, so each iteration gets a fresh variable.

    TypeScript has one numeric type, number, which is a double-precision float. It has no integer overflow, but it stops being exact for integers beyond 2^53. For this method, the results are exact up to F(78). From F(79) on the value is no longer a safe integer: fibonacci(79) gives 14472334024676220, while the true value ends in 221. The lesson's inputs stay well below that range. Far larger inputs, around n = 1477, make the result overflow to Infinity.

    Complexity

    The loop runs n - 1 times with constant work in each iteration, so the time is O(n). Only prev, curr, next and i are stored, so the extra space is O(1). The recursive definition, by contrast, makes an exponential number of calls without caching.

    Edge cases and common mistakes

    • n = 0 and n = 1. Without the early return, the loop would be skipped and curr would be 1, which is wrong for F(0).
    • n = 2. The loop runs once and returns 1.
    • Swapping in the wrong order. Assigning prev = curr after curr = next would set both to the new value and break the sequence.
    • Starting the loop at 1 or stopping at i < n. Either way the loop runs the wrong number of times and returns a neighbouring Fibonacci number.
    • Negative or fractional n. The lesson promises a non-negative integer. A negative n would pass the early check and be returned unchanged, which is not a sequence value, and the number type does not stop a caller from passing it. Validate the input if the method is used outside the lesson.

    Testing

    Try n = 0 (0), n = 1 (1), n = 10 (55) and n = 50 (12586269025).

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