Flatten Nested List Iterator Medium 0 attempts
LeetCode ↗

Flatten Nested List Iterator

Medium Stack&Queue LeetCode

You are given a nested list of integers. Each element is either an integer or a list whose elements may also be integers or other lists. Implement a function that flattens the nested list into a single flat array of integers in the order they appear.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]

Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Sample Input
—
Sample Output
—
Constraints
  • 1 <= nestedList.length <= 500
  • Values are in range [-10^6, 10^6]
Test Cases
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

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