A Solution to Leetcode problem 509. Fibonacci Number in JavaScript

Introduction:

The Fibonacci numbers are a series of numbers in which each number is the sum of the previous two numbers. The first two numbers in the series are usually defined as 0 and 1, and the subsequent numbers are calculated by adding the previous two numbers. For example, the Fibonacci sequence starting with 0 and 1 is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. In this post, we will be discussing a solution to the LeetCode problem #509: Fibonacci Number, using JavaScript.

Problem statement:

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

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

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

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

 Solution:

One way to solve this problem is to use a recursive approach, where we can define a function fib that returns the Fibonacci number for a given input n. The function will be called recursively with n-1 and n-2 as inputs until we reach the base case of n = 0 or n = 1, at which point we return 0 or 1 respectively.

Here is the implementation of this solution in JavaScript:

This solution has a time complexity of O(2^n) as we are making two recursive calls for each function call. The space complexity is also O(n) as the maximum depth of the recursive call stack is n.

A better solution would be to use an iterative approach, where we can use a loop to calculate the Fibonacci numbers and store them in an array. This way, we can avoid the recursive calls and achieve a time complexity of O(n).

Here is the implementation of this solution in JavaScript:

const fib = function(n) {
    let fibArr = [0, 1];
    for (let i = 2; i <= n; i++) {
        fibArr[i] = fibArr[i-1] + fibArr[i-2];
    }
    return fibArr[n];
};

We first create an array fibArr with the first two Fibonacci numbers (0 and 1). Then, we use a loop to iteratively calculate and store the subsequent Fibonacci numbers in the array. Finally, we return the nth element of the array as the result.

This solution has a time complexity of O(n) and a space complexity of O(n) as we are using an array to store the Fibonacci numbers.

Conclusion:

In this post, we discussed two solutions to the LeetCode problem #509: Fibonacci Number, using JavaScript. The first solution used a recursive approach with a time complexity of O(2^n) but second solution has a time complexity of o(n).