Start learning free

LESSON 181 OF 410 · LOOPS - CHALLENGES

Fibonacci Number in O(n) Time and O(1) Space using JavaScript

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

JAVASCRIPT · LOOPS - CHALLENGES

Fibonacci in JavaScript, explained

Understanding the Problem

The core challenge of this problem is to compute the nth Fibonacci number efficiently. The Fibonacci sequence is a classic example in computer science and has applications in various fields such as mathematics, computer algorithms, and even financial models. A common pitfall is using a naive recursive approach, which has exponential time complexity and is not feasible for large values of n.

Approach

To solve this problem efficiently, we need to avoid the naive recursive approach and instead use an iterative approach that runs in O(n) time and uses O(1) space.

Naive Solution

The naive solution involves using recursion:

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

While this solution is simple, it has exponential time complexity O(2^n) and is not suitable for large values of n.

Optimized Solution

We can optimize the solution by using an iterative approach with two variables to store the last two computed Fibonacci numbers. This approach runs in O(n) time and uses O(1) space.

Algorithm

1. Initialize two variables, prev and curr, to store the last two Fibonacci numbers. Set prev to 0 and curr to 1.

2. Iterate from 2 to n, updating the variables as follows:

Compute the next Fibonacci number as the sum of prev and curr.
Update prev to the value of curr.
Update curr to the value of the next Fibonacci number.

3. After the loop, curr will contain the nth Fibonacci number.

Code Implementation

function fibonacci(n) {
    // Handle base cases
    if (n === 0) return 0;
    if (n === 1) return 1;

    // Initialize the first two Fibonacci numbers
    let prev = 0;
    let curr = 1;

    // Iterate from 2 to n
    for (let i = 2; i <= n; i++) {
        // Compute the next Fibonacci number
        let next = prev + curr;
        // Update prev and curr
        prev = curr;
        curr = next;
    }

    // Return the nth Fibonacci number
    return curr;
}

Complexity Analysis

The time complexity of this approach is O(n) because we iterate from 2 to n. The space complexity is O(1) because we only use a constant amount of extra space for the variables prev and curr.

Edge Cases

Consider the following edge cases:

n = 0: The output should be 0.
n = 1: The output should be 1.

The algorithm handles these cases explicitly at the beginning.

Testing

To test the solution comprehensively, consider the following test cases:

n = 0: The output should be 0.
n = 1: The output should be 1.
n = 2: The output should be 1.
n = 3: The output should be 2.
n = 10: The output should be 55.
n = 20: The output should be 6765.

These test cases cover small values, typical values, and larger values of n.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem and constraints thoroughly.
Start with a naive solution to get a basic understanding.
Identify inefficiencies in the naive solution and think about how to optimize it.
Consider using iterative approaches to reduce time and space complexity.
Test your solution with a variety of test cases, including edge cases.

Conclusion

In this blog post, we discussed how to compute the nth Fibonacci number efficiently using an iterative approach. We covered the problem definition, naive and optimized solutions, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice problems related to the Fibonacci sequence, consider the following resources:

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

Start learning free