25. Flatten Nested List Iterator

hardAsked at Wix

Build a lazy iterator over an arbitrarily nested list structure — Wix's element hierarchy is a nested document tree, and this problem tests whether you can traverse it on-demand without materialising the full flat list, which matters for large pages.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

You are given a nested list of integers nestedList where each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator that flattens it: next() returns the next integer, hasNext() returns true if integers remain. The NestedInteger interface has isInteger(), getInteger(), and getList().

Constraints

1 <= nestedList.length <= 500
The nesting depth is at most 30
-10^6 <= integer values <= 10^6

Examples

Example 1

Input

nestedList = [[1,1],2,[1,1]]

Output

[1,1,2,1,1]

Explanation: hasNext/next calls in sequence produce the flattened integers

Example 2

Input

nestedList = [1,[4,[6]]]

Output

[1,4,6]

Approaches

1. Pre-flatten at construction

Recursively flatten the entire nested list into an array at construction time. next() and hasNext() are then O(1) array operations.

Time: O(N) construction, O(1) next/hasNext
Space: O(N)

class NestedIterator {
  constructor(nestedList) {
    this.flat = [];
    this.index = 0;
    this._flatten(nestedList);
  }
  _flatten(list) {
    for (const item of list) {
      if (item.isInteger()) {
        this.flat.push(item.getInteger());
      } else {
        this._flatten(item.getList());
      }
    }
  }
  next() {
    return this.flat[this.index++];
  }
  hasNext() {
    return this.index < this.flat.length;
  }
}

Tradeoff:

2. Lazy stack iterator

Push the top-level list onto a stack as an iterator. On hasNext, repeatedly peek: if the front element is an integer, return true; if it's a nested list, expand it and push a new iterator. This avoids flattening elements we may never reach.

Time: O(1) amortised next/hasNext
Space: O(depth)

class NestedIterator {
  constructor(nestedList) {
    // Stack holds iterators (arrays with an index pointer)
    this.stack = [{ list: nestedList, i: 0 }];
  }
  _advance() {
    while (this.stack.length) {
      const top = this.stack[this.stack.length - 1];
      if (top.i >= top.list.length) {
        this.stack.pop();
        continue;
      }
      const item = top.list[top.i];
      if (item.isInteger()) return; // ready to yield
      top.i++;
      this.stack.push({ list: item.getList(), i: 0 });
    }
  }
  hasNext() {
    this._advance();
    return this.stack.length > 0;
  }
  next() {
    this._advance();
    const top = this.stack[this.stack.length - 1];
    return top.list[top.i++].getInteger();
  }
}

Tradeoff:

Wix-specific tips

Wix's document model is deeply nested — sections contain columns, columns contain elements, elements contain sub-elements. The lazy stack approach is the one Wix's platform team would write in production, because it lets you pause traversal between renders and avoid blocking the main thread when iterating large page trees. Lead with the lazy version and explain the deferred-work benefit.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Flatten Nested List Iterator and other Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →