Skip to main content

25. Flatten Nested List Iterator

mediumAsked at Dropbox

Build a lazy iterator that traverses a recursive list structure depth-first — Dropbox engineers recognize this pattern immediately as a model for walking a nested folder hierarchy without loading all entries into memory at once.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer or a list whose elements may also be integers or other lists. Implement NestedIterator with hasNext() and next() methods. next() returns the next integer; hasNext() returns true if there are still integers to iterate.

Constraints

  • 1 <= nestedList.length <= 500
  • The values of the integers are in the range [-10^6, 10^6]
  • The total depth of nesting is at most 50

Examples

Example 1

Input
nestedList = [[1,1],2,[1,1]]
Output
[1,1,2,1,1]

Explanation: Flattening the nested structure yields the integers in depth-first order.

Example 2

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

Approaches

1. Flatten eagerly on construction

Recursively flatten the entire nested list into a plain array during construction, then serve elements from a pointer. Simple but uses O(n) extra space upfront.

Time
O(n) construction, O(1) per call
Space
O(n)
class NestedIterator {
  constructor(nestedList) {
    this.flat = [];
    this.idx = 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.idx++];
  }
  hasNext() {
    return this.idx < this.flat.length;
  }
}

Tradeoff:

2. Stack-based lazy iterator

Push all top-level items onto a stack in reverse order. On hasNext(), peel nested lists off the stack by expanding the top item until an integer is on top. Truly lazy — never processes more than needed.

Time
O(1) amortized per call
Space
O(d) where d = max nesting depth
class NestedIterator {
  constructor(nestedList) {
    this.stack = [...nestedList].reverse();
  }
  hasNext() {
    while (this.stack.length > 0) {
      const top = this.stack[this.stack.length - 1];
      if (top.isInteger()) return true;
      this.stack.pop();
      const expanded = top.getList().reverse();
      for (const item of expanded) {
        this.stack.push(item);
      }
    }
    return false;
  }
  next() {
    return this.stack.pop().getInteger();
  }
}

Tradeoff:

Dropbox-specific tips

Dropbox specifically cares about the lazy variant — in their file system context, eagerly reading an entire directory tree is too expensive. Explain that the stack approach mirrors a depth-first traversal where you defer expanding a subtree until you actually need the next element, which maps directly to paginated folder listings.

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 Dropbox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →