Leetcode 509. Fibonacci Number

Problem Explanation

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, starting from 0 and 1. This problem focuses on finding the Nth Fibonacci number in the sequence. For instance, if N is 3, F(N) would be equal to F(3) = F(2) + F(1) = 1 + 1 = 2. The solution needs to accommodate for values of N ranging from 0 to 30, inclusive.

The approach here is to implement a dynamic programming solution that utilizes memoization, an optimization technique used primarily to speed up program execution by storing the results of expensive function calls and reusing them when necessary, rather than recomputing the results each time.

An array (in Python, called a list) is created to store the already computed values of the Fibonacci sequence. Since the first two numbers of the Fibonacci sequence are 0 and 1, these values are initialized in the list. Then, a loop is used to calculate each subsequent Fibonacci number and store them in the list.

In this problem, three indices of the list are used to calculate the Fibonacci numbers. The first index holds the current Fibonacci number, the second index holds the current number plus the previous one, and the third index holds the sum of the first two indexes. By shifting these indices in each iteration, all Fibonacci numbers are calculated until the Nth Fibonacci number is reached.

On the practical example with N=4:

0th Fibonacci number is 0 1st Fibonacci number is 0+1=1 2nd Fibonacci number is 1+1=2

3rd Fibonacci number is 1+2=3 We've reached our N

The problem description example:

1Fibonacci Sequence: 0, 1, 1, 2, 3
2F(4) = F(3) + F(2)
3F(4) = 3

Python Solution

1
2python
3class Solution:
4    def fib(self, N: int) -> int:
5        if N < 2:
6            return N
7        dp = [0, 0, 1]
8        for i in range(2, N+1):
9            dp[0] = dp[1]
10            dp[1] = dp[2]
11            dp[2] = dp[0] + dp[1]
12        return dp[-1]

Java Solution

1
2java
3class Solution {
4    public int fib(int N) {
5        if (N < 2) {
6            return N;
7        }
8        int[] dp = new int[]{0, 0, 1};
9        for (int i = 2; i <= N; i++) {
10            dp[0] = dp[1];
11            dp[1] = dp[2];
12            dp[2] = dp[0] + dp[1];
13        }
14        return dp[2];
15    }
16}

JavaScript Solution

1
2javascript
3var fib = function(N) {
4    if (N < 2) {
5        return N;
6    }
7    let dp = [0, 0, 1];
8    for(let i = 2; i <= N; ++i){
9        dp[0] = dp[1];
10        dp[1] = dp[2];
11        dp[2] = dp[0] + dp[1];
12    }
13    return dp[2];
14};

C++ Solution

1
2c++
3class Solution {
4public:
5    int fib(int N) {
6        if (N < 2) {
7            return N;
8        }
9        vector<int> dp(3, 0);
10        dp[2] = 1;
11        for (int i = 2; i <= N; ++i) {
12            dp[0] = dp[1];
13            dp[1] = dp[2];
14            dp[2] = dp[0] + dp[1];
15        }
16        return dp[2];
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int Fib(int N) {
5        if (N < 2) {
6            return N;
7        }
8        int[] dp = new int[] {0, 0, 1};
9        for (int i = 2; i <= N; ++i) {
10            dp[0] = dp[1];
11            dp[1] = dp[2];
12            dp[2] = dp[0] + dp[1];
13        }
14        return dp[2];
15    }
16}

The solutions iterate through the Fibonacci sequence, storing newly calculated numbers in the dp array. When the last number is calculated it is then returned as the "Nth" Fibonacci number.# Conclusion

Generally, the Fibonacci number finding algorithm is a common problem that is frequently asked in coding interviews - it becomes an important task to solve it efficiently like the solutions above in various programming languages. The use of Dynamic Programming and Memoization to reduce time complexity and achieve runtime efficiency proves to be critical here.

This Fibonacci number finding algorithm's complexity is linear, O(N), so it can handle large input sizes with speeds.

Each function works like this: For an input integer N, if N is less than 2 the function simply returns N itself because the Fibonacci sequence starts with 0 and 1. If the input is equal to or greater than 2, an array of length 3 (dp) is initialized with [0,0,1]. It then performs a loop from 2 to N (inclusive). Within each round of iteration, the first and second indices of the array slide over one index, and the third index becomes the sum of the values stored in the first two indices, simulating the Fibonacci sequence.

This simple, optimized approach to finding Fibonacci numbers is very effective and practical for both small and large input values. It minimizes memory usage by only ever storing three Fibonacci numbers at once and allows coders in a wide range of programming languages to accomplish the same goal with slight syntax variations.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫