The O(n) Club: Taming LeetCode’s Flatten Nested List Iterator Without Losing Your Mind

The O(n) Club: Taming LeetCode’s Flatten Nested List Iterator Without Losing Your Mind

⚡ TL;DR

If you thought recursion was wild, try feeding a list of lists of lists (…of more lists) into an iterator and getting out actual integers. You want to flatten everything? Go DFS, dump it all in an ArrayList, and just index your way to freedom.

// Flatten everything up front
List<Integer> flat = new ArrayList<>();
flatten(nestedList, flat);
int idx = 0; // next() just returns flat.get(idx++)
 void flatten(List<NestedInteger> input, List<Integer> out) {
    for (NestedInteger ni : input)
        if (ni.isInteger()) out.add(ni.getInteger());
        else flatten(ni.getList(), out);
}

🧠 How Devs Usually Mess This Up

Most folks panic and recursively unload every integer into a list, which is great — until your input is basically the Matrix but with empty lists. Or they build some half-baked stack solution but forget that hasNext() and next() need to stay in sync, so integers vanish into thin air. Some even try mutating the input mid-traversal. (Spoiler: your interviewer is keeping score.)

🔍 What’s Actually Going On

Picture opening nested boxes, each with more boxes inside, all the way down. Sometimes there are numbers, sometimes it’s just more packing peanuts. You’re basically playing Russian dolls with your CPU — and that’s before empty lists drop in to crash the party. The point: each call to next() should give the next integer, no matter how deep it’s buried, without ever losing your place.

The debate: Pre-flatten with a DFS and walk an ArrayList, or use a stack to flatten the list as you iterate. DFS is easy but gobbles memory if the input’s huge. Stack-based on-demand flattening is leaner but needs you to handle iterator state like you actually care about edge cases.

🛠️ PseudoCode

• Pre-flattening Approach:
  • Recursively traverse the whole nest upfront (DFS)
  • On integer: add to flat list
  • On list: recurse
  • Set index to 0; next() is flat.get(idx++); hasNext() is idx < flat.size()

  void flatten(nestedList, result) {
    for (NestedInteger ni : nestedList)
      if (ni.isInteger()) result.add(ni.getInteger());
      else flatten(ni.getList(), result);
  }
  

• Stack-based (On-Demand) Approach:
  • Stack holds NestedInteger elements in reverse order
  • hasNext():
    • While top is a list, pop and push its items in reverse
    • If top is integer: ready for next()
  • next(): pop and return top integer

  public boolean hasNext() {
      while (!stack.isEmpty()) {
          NestedInteger current = stack.peek();
          if (current.isInteger()) return true;
          stack.pop();
          List<NestedInteger> list = current.getList();
          for (int i = list.size() - 1; i >= 0; i--) stack.push(list.get(i));
      }
      return false;
  }
  

💻 The Code

// Assume NestedInteger interface is given with isInteger(), getInteger(), getList().
public class NestedIterator implements Iterator<Integer> {
    private Deque<NestedInteger> stack;
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new ArrayDeque<>();
        pushList(nestedList);
    }
    private void pushList(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            stack.push(list.get(i));
        }
    }
    @Override
    public Integer next() {
        if (!hasNext()) throw new NoSuchElementException();
        return stack.pop().getInteger();
    }
    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            NestedInteger top = stack.peek();
            if (top.isInteger()) return true;
            stack.pop();
            pushList(top.getList());
        }
        return false;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If you try modifying the nested input list as you iterate, expect nightmares worthy of a Kafka novel.
• Edge cases: [[], [[[]]], 5] — empty lists that only exist to ruin your test coverage stats.
• Stack iterator is slower to start if first integer is nowhere near the surface, but is stingy with memory for colossal/deeply nested data.
• Each integer gets visited once. Pre-flattening: — space O(n), time O(n). Stack: space O(depth), time O(total).

🧠 Interviewer Brain-Tattoo

“Anyone can recurse. Only the brave flatten lazily, without ever losing count.” (Write it on your monitor in Sharpie.)