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 <= 50Problem 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.
This approach uses an iterative method to generate Fibonacci numbers. The idea is to maintain two variables representing the last two numbers in the sequence and update them in each iteration.
This code defines a generator function fib_generator() which yields Fibonacci numbers indefinitely. It initializes two variables a and b to 0 and 1 (first two Fibonacci numbers) and then enters an infinite loop where it yields a and updates a, b to the next two numbers in the sequence.
Python
JavaScript
Time Complexity: O(1) per yield.
Space Complexity: O(1).
This approach uses recursion to generate Fibonacci numbers. This approach is more intuitive but is less common due to the overhead of recursive calls.
This C++ solution emulates generator behavior using a class called Fibonacci. The class maintains state between calls using private member variables a and b, similar to static variables in a recursive function. The function next() returns the next Fibonacci number.
Time Complexity: O(1) per call.
Space Complexity: O(1).
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Generator | Time Complexity: O(1) per yield. |
| Approach 2: Recursive Generator | Time Complexity: O(1) per call. |
| Default Approach | — |
| 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. |
Generate Fibonacci Sequence - Leetcode 2648 - JavaScript 30-Day Challenge • NeetCodeIO • 7,873 views views
Watch 7 more video solutions →Practice Generate Fibonacci Sequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor