💬 Discord
Sign In
NeetCode #972LC-2648EasyJavaScript
← Back to All Problems

#972 · #2648 · Generate Fibonacci Sequence(生成斐波那契数列)

📌 Problem Statement & Constraints

Implement the generator function fibGenerator(), which yields the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, ... one value per next() call, without bound.

💡 Core Algorithmic Approaches

  1. Declare it with function* and an infinite while (true) loop containing yield.
  2. Keep two variables a and b (starting at 0 and 1); yield a, then update with [a, b] = [b, a + b].
  3. Destructuring assignment evaluates the right side first, so the swap is atomic and does not clobber either value.
  4. Generators support lazy evaluation, so no array needs to be preallocated.

💻 Benchmark Python3 Implementation

var fibGenerator = function*() {
    let a = 0, b = 1;
    while (true) {
        yield a;                              // emit the current term
        [a, b] = [b, a + b];                  // right side evaluates first: safe swap
    }
};

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): constant time per next().
💾 Space Complexity
O(1): only two variables are kept.

⚠️ Interview Pitfalls & Follow-ups

  • Writing a = b; b = a + b;: the second line uses the already-updated a, giving wrong values.
  • Pre-generating an array and returning it: an infinite sequence cannot be materialised.
  • Omitting the while (true) loop: only a single value would be produced.
  • Returning an array from a normal function: the problem requires a generator with a next() interface.