Flatten Nested List Iterator
Medium · Stack & Strings · Stack · Tree · Depth-First Search · Design · Queue · Iterator
Problem
You are given a nested list of integers nestedList: each element is either an integer or a list, whose elements may again be integers or lists. Implement an iterator that returns the integers one at a time in left-to-right order.
Implement the class NestedIterator:
- NestedIterator(nestedList) sets up the iterator over nestedList, a list of NestedInteger elements.
- next() returns the next integer.
- hasNext() returns True if integers remain and False otherwise.
A NestedInteger element e offers e.isInteger(), e.getInteger() (the integer, or None for a list) and e.getList() (the list, or None for an integer).
The grader calls hasNext() (twice in a row, so asking must not consume anything) and then next(), in a loop, collects every integer, and compares the collected list with the flattened input.
Examples
Input: nestedList = [[5,[6]],7] Output: [5,6,7]
Reading left to right: inside the first list come 5 and then the list [6]; after it comes 7.
Input: nestedList = [[],[8,[]],[[9]]] Output: [8,9]
Empty lists contribute nothing, however deeply they sit.
Input: nestedList = [1,[2,[3,[4]]]] Output: [1,2,3,4]
Each level holds one integer and one deeper list.
Constraints
- 1 <= len(nestedList) <= 500
- At most 10^4 integers in total
- Every integer is in [-10^6, 10^6]
- Nesting depth at most 200
Approaches
- Flatten everything in the constructor — time O(N + L) up front, O(1) per call, space O(N + D)
Follow-up
Python generators make this a few lines: a recursive generator that yields integers and yield froms nested lists, with one value buffered so hasNext() can peek. The generator keeps the same stack of paused frames for you.
Related problems
Start free on Cariara · Coding problems · System design studio
