LeetCode 2648 - Generate Fibonacci Sequence

The problem asks us to implement a generator function that yields numbers from the Fibonacci sequence. The Fibonacci sequence is defined recursively as Xn = Xn-1 + Xn-2 with the starting values X0 = 0 and X1 = 1.

leetcodeeasy

LeetCode Problem 2648

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

The problem asks us to implement a generator function that yields numbers from the Fibonacci sequence. The Fibonacci sequence is defined recursively as Xn = Xn-1 + Xn-2 with the starting values X0 = 0 and X1 = 1. Essentially, each number in the sequence is the sum of the two preceding numbers.

The input in this problem is not directly passed to the function, but rather the sequence is generated lazily using a generator object. The callCount in the examples represents the number of times the generator’s next() method is called. For example, if callCount = 5, the first five Fibonacci numbers [0,1,1,2,3] should be produced sequentially by the generator.

The constraints are small: 0 <= callCount <= 50, so performance is not a major concern. However, the solution must correctly yield numbers in order and handle zero calls, which should produce no output.

Edge cases include callCount = 0 (should produce nothing), callCount = 1 (should yield only 0), and the transition from the first two numbers to the standard recursive sum.

Approaches

The brute-force approach would be to precompute the Fibonacci sequence up to the maximum callCount and return numbers from an array. This works because the sequence is small and the number of calls is limited. The drawback is that it precomputes and stores numbers unnecessarily if the generator is called fewer times, and it is less memory-efficient.

The optimal approach leverages Python or Go generators, yielding Fibonacci numbers one at a time. Instead of storing the entire sequence, it keeps only the last two numbers in memory, computes the next number on demand, and yields it. This is efficient in both time and space and aligns perfectly with the lazy evaluation paradigm of generators.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Precomputes all Fibonacci numbers up to n and stores them in a list
Optimal O(n) O(1) Uses a generator and stores only the last two numbers, yielding on demand

Algorithm Walkthrough

  1. Initialize two variables a and b with the first two Fibonacci numbers 0 and 1. These variables will track the last two numbers in the sequence.
  2. Enter an infinite loop, since a generator can be called an arbitrary number of times. In each iteration, yield a as the next Fibonacci number.
  3. Update the two variables: set a to b, and b to a + b. This effectively shifts the sequence forward by one step.
  4. Repeat the loop, allowing the generator to lazily produce numbers each time next() is called.
  5. Because generators are lazy, no numbers are computed until the consumer requests them, handling the callCount = 0 edge case naturally.

Why it works: At each step, a always holds the next Fibonacci number to yield. The invariant is that a and b represent two consecutive Fibonacci numbers. Updating them in order ensures that the sequence remains correct indefinitely.

Python Solution

from typing import Generator

class Solution:
    def fibGenerator(self) -> Generator[int, None, None]:
        a, b = 0, 1
        while True:
            yield a
            a, b = b, a + b

The Python implementation uses a generator function, which allows lazy evaluation of the Fibonacci sequence. We initialize the first two numbers and then enter an infinite loop. Each iteration yields the current number and updates the state for the next Fibonacci number. This directly corresponds to the algorithm steps above and automatically handles any number of calls, including zero.

Go Solution

package main

func fibGenerator() func() int {
    a, b := 0, 1
    return func() int {
        result := a
        a, b = b, a+b
        return result
    }
}

In Go, we implement a closure that keeps track of the last two Fibonacci numbers. Each call to the returned function yields the next number in the sequence. Unlike Python, Go does not have native generators, so we use a closure to mimic the same lazy evaluation behavior. Edge cases are handled naturally because the state is initialized correctly and updates on every call.

Worked Examples

Example 1: callCount = 5

Step a b Yielded
1 0 1 0
2 1 1 1
3 1 2 1
4 2 3 2
5 3 5 3

Output: [0,1,1,2,3]

Example 2: callCount = 0

No calls to next(), no numbers are yielded. Output: []

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each next() call computes the next Fibonacci number in constant time, n calls total
Space O(1) Only two variables are maintained, regardless of the number of calls

The generator approach ensures minimal memory usage while computing numbers on demand, which is ideal for lazy evaluation scenarios.

Test Cases

gen = Solution().fibGenerator()
assert [next(gen) for _ in range(5)] == [0,1,1,2,3]  # Example 1
gen = Solution().fibGenerator()
assert [next(gen) for _ in range(0)] == []           # Example 2
gen = Solution().fibGenerator()
assert [next(gen) for _ in range(1)] == [0]          # Single call
gen = Solution().fibGenerator()
assert [next(gen) for _ in range(2)] == [0,1]        # First two numbers
gen = Solution().fibGenerator()
assert [next(gen) for _ in range(10)] == [0,1,1,2,3,5,8,13,21,34]  # Larger sequence
Test Why
callCount = 5 Validates standard small sequence
callCount = 0 Validates zero calls edge case
callCount = 1 Validates single element output
callCount = 2 Validates first two elements correctness
callCount = 10 Validates correctness for longer sequences

Edge Cases

One important edge case is callCount = 0, which tests that the generator correctly handles no calls without errors. The Python generator and Go closure both naturally yield nothing until called, so this is handled automatically.

Another edge case is the transition from the first two numbers to the sum pattern. The first two numbers are 0 and 1, which do not follow the sum rule for initialization. The implementation correctly initializes these values so that the third number onwards follows the Fibonacci relation.

Finally, the generator must handle sequences longer than the first few elements without integer overflow in Python, which is handled automatically due to Python’s arbitrary-precision integers. In Go, integers can overflow for large sequences, but the problem constraints callCount <= 50 ensure that this will not happen, so no special handling is required.