Flatten Nested List Iterator Medium 0 attempts
LeetCode ↗

Flatten Nested List Iterator

Medium Stack&Queue LeetCode

You're given a nested list where each entry is either a plain integer or another nested list, which may itself contain integers or further nested lists to any depth. Implement NestedIterator with hasNext() and next() to traverse the integers lazily in left-to-right order. Call next() only when hasNext() is true. The editor drains the iterator into an array for comparison.

Input Format
Implement NestedIterator(nestedList). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Implement hasNext() and next(). The editor displays the fully drained iterator as an array.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
nestedList = [1,[4,[6]]]
Output
[1,4,6]
Constraints
  • 1 <= nestedList.length <= 500
  • Values are in range [-10^6, 10^6]
Test Cases (2)
Case 1
Args: [[[1,1],2,[1,1]]] Expected: [1,1,2,1,1]
Case 2
Args: [[1,[4,[6]]]] Expected: [1,4,6]
Topics
Stack&Queue

Stack with Lazy Flattening

javascript
class NestedIterator {
  constructor(nestedList) { this.stack = [...nestedList].reverse(); }
  hasNext() {
    while (this.stack.length) {
      const top = this.stack[this.stack.length - 1];
      if (typeof top === 'number') return true;
      this.stack.pop();
      for (let i = top.length - 1; i >= 0; i--) this.stack.push(top[i]);
    }
    return false;
  }
  next() { return this.stack.pop(); }
}

Time: O(1) amortized | Space: O(n)

Saved in this browser only. Private to you.

JavaScript