Skip to main content
Talentd

Generate Fibonacci Sequence - Solution & Explanation

Easy5 min readAsked at: Google, Bloomberg
Practice this problem

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.

Approach 1: Approach 1: Iterative Generator

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(1) per yield.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Approach 2: Recursive Generator

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.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(1) per call.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Iterative Generator

Time Complexity: O(1) per yield.
Space Complexity: O(1).

Approach 2: Recursive Generator

Time Complexity: O(1) per call.
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative GeneratorO(n)O(1)Best general solution. Minimal memory and straightforward logic.
Recursive GeneratorO(n)O(n)Useful for demonstrating the Fibonacci recurrence or recursion concepts.

Video Solution

Generate Fibonacci Sequence - Leetcode 2648 - JavaScript 30-Day Challenge • NeetCodeIO • 8,038 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Generate Fibonacci Sequence easy or hard?
Generate Fibonacci Sequence is generally classified as an easy problem. The core logic involves computing each number as the sum of the previous two, which can be implemented with a simple loop or generator.
Generate Fibonacci Sequence Python/Java solution
In Python or JavaScript, this problem is typically solved using generator functions that yield Fibonacci numbers one at a time. In C++ or C#, the sequence can be produced using recursion or iterative loops that return values incrementally.
How to solve Generate Fibonacci Sequence in O(n)?
Maintain two variables representing consecutive Fibonacci numbers. On every step, yield the current number and update the pair using a simple addition and shift operation. Since each value is calculated once, the total time complexity remains O(n).
What is the best approach for Generate Fibonacci Sequence?
The iterative generator approach is the best solution. It computes each Fibonacci number using two running variables and yields the result immediately. This achieves O(n) time complexity and O(1) extra space because only the last two values are stored.
Is Generate Fibonacci Sequence asked at Google/Amazon/Meta?
Fibonacci-related problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. They are often used to evaluate understanding of recursion, iteration, dynamic programming fundamentals, and space optimization.
What data structure is used in Generate Fibonacci Sequence?
No complex data structure is required. The optimal solution relies on two integer variables that track the previous two Fibonacci numbers. When implemented as a generator, it produces values lazily without storing the entire sequence.
What is the time complexity of Generate Fibonacci Sequence?
Generating the first n Fibonacci numbers takes O(n) time because each new value is computed once using a constant-time addition. The iterative approach uses O(1) auxiliary space, while the recursive generator uses O(n) stack space.

Ready to solve this problem?

Practice Generate Fibonacci Sequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Cancellable Function

Next

Nested Array Generator