26. Flatten Nested List Iterator

mediumAsked at Box

Produce a lazy iterator over a deeply nested list — this mirrors how Box's content API streams a recursively nested folder tree to clients one file at a time without loading the full hierarchy into memory.

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

Problem

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it. Implement the NestedIterator class: NestedIterator(nestedList) initializes the iterator with the nested list. next() returns the next integer. hasNext() returns true if there are still integers in the structure.

Constraints

1 <= nestedList.length <= 500
The values of the integers in the nested list are in the range [-10^6, 10^6]

Examples

Example 1

Input

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

Output

[1,1,2,1,1]

Explanation: By calling next repeatedly until hasNext returns false, the order is: 1, 1, 2, 1, 1.

Example 2

Input

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

Output

[1,4,6]

Approaches

1. Brute force — eager flatten

Recursively flatten the entire nested list into a plain array up front; then use a pointer to serve next() calls.

Time: O(n) constructor
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. Optimal — lazy stack iterator

Push the entire list onto a stack as iterators. hasNext() advances the top iterator, expanding any nested list it finds, until an integer is at the front — true lazy evaluation.

Time: O(1) amortized per call
Space: O(depth)

class NestedIterator {
  constructor(nestedList) {
    // Stack of [list, index] pairs
    this.stack = [[nestedList, 0]];
  }
  hasNext() {
    while (this.stack.length) {
      const [list, i] = this.stack[this.stack.length - 1];
      if (i >= list.length) {
        this.stack.pop();
        continue;
      }
      const item = list[i];
      if (item.isInteger()) return true;
      // Expand nested list
      this.stack[this.stack.length - 1][1]++; // advance parent
      this.stack.push([item.getList(), 0]);
    }
    return false;
  }
  next() {
    const [list, i] = this.stack[this.stack.length - 1];
    this.stack[this.stack.length - 1][1]++;
    return list[i].getInteger();
  }
}

Tradeoff:

Box-specific tips

Box interviewers specifically value the lazy stack solution because it maps to how their content API paginates deeply nested folder trees — you never materialize the full subtree. Expect the follow-up: 'What happens if a collaborator adds files mid-iteration?' Walk through how you'd handle live mutations on the underlying list, which is a real design concern in Box's collaborative editing environment.

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

Practice these live with InterviewChamp.AI →