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 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.
Constraints:
0 <= n <= 30The Fibonacci Number problem asks you to compute the nth value in the Fibonacci sequence, where each number is the sum of the previous two. A straightforward approach is recursive computation, which directly follows the mathematical definition: F(n) = F(n-1) + F(n-2). However, this naive recursion recalculates the same values many times, leading to exponential time complexity.
A more efficient strategy is memoization, where previously computed Fibonacci values are stored and reused. This avoids repeated work and reduces the time complexity to linear time. Another common technique is bottom-up dynamic programming, where the sequence is built iteratively from the base cases upward.
For further optimization, you can keep only the last two Fibonacci values instead of storing the entire array. This space-optimized iterative approach achieves O(n) time and O(1) space, making it the most practical solution for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive Recursion | O(2^n) | O(n) |
| Memoization (Top-Down DP) | O(n) | O(n) |
| Iterative DP (Space Optimized) | O(n) | O(1) |
NeetCode
The recursive approach involves directly applying the Fibonacci formula: F(n) = F(n-1) + F(n-2). This approach naturally follows the definition of the Fibonacci sequence, solving subproblems by calling itself. However, this naive implementation leads to overlapping subproblems and higher time complexity.
This recursive solution is easy to implement but inefficient for larger n due to exponential time complexity.
Time Complexity: O(2^n) because it grows exponentially, with overlapping subproblems.
Space Complexity: O(n) due to the recursion stack required by function calls.
1function fibonacci(n) {
2 if (n <= 1) return n;
3 return fibonacci(n - 1) + fibonacci(n
This JavaScript function defines 'fibonacci' recursively computing the nth Fibonacci number. It checks for the base case and performs recursive calls analogous to other language solutions.
The dynamic programming approach involves using an array to store previously computed Fibonacci numbers, which prevents redundant calculations found in the recursive approach. This method significantly improves efficiency by transforming the exponential recursive solution into a linear solution, using merely linear space.
Time Complexity: O(n) due to linear iteration.
Space Complexity: O(n) for the array storing Fibonacci numbers.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach is an iterative dynamic programming method that keeps track of only the last two Fibonacci values. This reduces space usage while maintaining O(n) time complexity, making it efficient for interview scenarios.
Recursion matches the mathematical definition of Fibonacci but is inefficient in its naive form because it recomputes the same values many times. Using memoization with recursion can significantly improve performance.
Yes, Fibonacci is a classic interview question used to test understanding of recursion, dynamic programming, and optimization techniques. It often appears as a foundational problem in coding interviews.
Memoization typically uses an array or hash map to store previously computed Fibonacci values. This allows the algorithm to reuse results instead of recalculating them repeatedly.
In Java, a similar iterative approach is used. 'fib[]' stores Fibonacci numbers computed so far. The nth Fibonacci number is returned, eliminating the function call overhead of recursion.