Generate Fibonacci Sequence - Leetcode 2648 - JavaScript 30-Day Challenge
Generate Fibonacci Sequence - Video Solution
Watch 6 video solutions for Generate Fibonacci Sequence, a easy level problem. This walkthrough by NeetCodeIO has 8,038 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Write a generator function that returns a generator object which yields the fibonacci sequence.
The fibonacci sequence is defined by the relation Xn = Xn-1 + Xn-2.
The first few numbers of the series are 0, 1, 1, 2, 3, 5, 8, 13.
Example 1:
Input: callCount = 5 Output: [0,1,1,2,3] Explanation: const gen = fibGenerator(); gen.next().value; // 0 gen.next().value; // 1 gen.next().value; // 1 gen.next().value; // 2 gen.next().value; // 3
Example 2:
Input: callCount = 0 Output: [] Explanation: gen.next() is never called so nothing is outputted
Constraints:
0 <= callCount <= 50
Approach Overview
Problem Overview: Generate Fibonacci numbers sequentially using a generator. Each call returns the next number in the sequence where F(n) = F(n-1) + F(n-2), starting with 0 and 1.
Approach 1: Iterative Generator (Time: O(n), Space: O(1))
This approach maintains two variables representing the previous two Fibonacci values. On each iteration, yield the current value and update the pair using simple assignment: next = a + b, then shift the window forward. The generator continues indefinitely or until the required number of values is produced. This works because Fibonacci depends only on the two previous numbers, so you never need the full sequence in memory. It’s the most practical approach and demonstrates strong understanding of iteration and generator mechanics.
Approach 2: Recursive Generator (Time: O(n), Space: O(n))
A recursive generator models the mathematical definition directly. The base cases yield the first two Fibonacci numbers. For subsequent values, the function recursively generates earlier values and combines them to produce the next number. Because each recursive call remains on the call stack until completion, space usage grows linearly with the number of generated elements. This version highlights concepts from recursion and lazy sequence generation with generators, but it introduces overhead compared to the iterative approach.
Recommended for interviews: The iterative generator is what interviewers expect. It runs in O(n) time with O(1) auxiliary space and clearly shows you understand how Fibonacci depends only on the previous two values. Discussing the recursive version still helps demonstrate conceptual understanding of the recurrence relation, but the iterative generator shows stronger practical coding skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Generator | O(n) | O(1) | Best general solution. Minimal memory and straightforward logic. |
| Recursive Generator | O(n) | O(n) | Useful for demonstrating the Fibonacci recurrence or recursion concepts. |