Flatten Nested List Iterator
Flatten Nested List Iterator is a medium design data structures problem solved with the stack pattern.
The best approach, optimal (lazy stack of cursors), runs in O(1) amortized per call time and O(D) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flatten everything up front) up.
Problem
You are given a nested list of integers nestedList. Every element is either an integer or another list, whose elements can again be integers or lists, to any depth.
Implement the NestedIterator class, which walks through all the integers in reading order (left to right, going inside each sub-list where it appears):
NestedIterator(nestedList)creates the iterator over the given nested list.next()returns the next integer.hasNext()returnstrueif there are integers left,falseotherwise.
You may only inspect the structure through the NestedInteger interface: isInteger() tells you whether the element holds a single integer, getInteger() returns that integer, and getList() returns the element’s list. The judge creates the iterator and keeps calling hasNext() and next(); your output is correct if the sequence of returned integers equals the flattened list.
Examples
Example 1
- Input
nestedList = [[4, 1], 6, [[2]]]- Output
[4, 1, 6, 2]- Why
- Calling hasNext() and next() until hasNext() is false returns the integers in reading order: 4, 1, 6, 2.
Example 2
- Input
nestedList = [7, [], [[-3, [8]]], []]- Output
[7, -3, 8]- Why
- Empty lists contribute nothing; the deeply nested -3 and 8 still come out in order.
Example 3
- Input
nestedList = [[], [[]]]- Output
[]- Why
- There are no integers at all, so the very first hasNext() returns false.
Constraints
1 <= nestedList.length <= 500- Integers are in the range
[-10^6, 10^6]. - Lists can be nested up to 500 levels deep and may be empty.
- next() is only called when hasNext() would return true.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (flatten everything up front) | O(N) constructor, O(1) next/hasNext | O(N) |
| Optimal (lazy stack of cursors) | O(1) amortized per call | O(D) |
1Brute force (flatten everything up front)
O(N) constructor, O(1) next/hasNextN is the number of integers plus lists. Every element is visited once while flattening; after that each call is a single index operation.O(N)The flat copy holds all integers, and the recursion goes as deep as the nesting.In the constructor, walk the whole structure recursively and copy every integer into one flat list. The iterator is then just an index into that list.
- Constructor: call flatten(nestedList), which appends integers and recurses into sub-lists.
- hasNext(): return pos < values.size().
- next(): return values.get(pos++).
class NestedIterator implements Iterator<Integer> {
private final List<Integer> values = new ArrayList<>();
private int pos = 0;
public NestedIterator(List<NestedInteger> nestedList) {
flatten(nestedList);
}
private void flatten(List<NestedInteger> list) {
for (NestedInteger ni : list) {
if (ni.isInteger()) values.add(ni.getInteger());
else flatten(ni.getList());
}
}
@Override
public Integer next() {
return values.get(pos++);
}
@Override
public boolean hasNext() {
return pos < values.size();
}
}class NestedIterator:
def __init__(self, nestedList: List["NestedInteger"]):
self.values = []
self.pos = 0
self.flatten(nestedList)
def flatten(self, lst: List["NestedInteger"]) -> None:
for ni in lst:
if ni.isInteger():
self.values.append(ni.getInteger())
else:
self.flatten(ni.getList())
def next(self) -> int:
v = self.values[self.pos]
self.pos += 1
return v
def hasNext(self) -> bool:
return self.pos < len(self.values)class NestedIterator {
vector<int> values;
size_t pos = 0;
void flatten(const vector<NestedInteger>& list) {
for (const auto& ni : list) {
if (ni.isInteger()) values.push_back(ni.getInteger());
else flatten(ni.getList());
}
}
public:
NestedIterator(vector<NestedInteger>& nestedList) {
flatten(nestedList);
}
int next() {
return values[pos++];
}
bool hasNext() {
return pos < values.size();
}
};class NestedIterator {
constructor(nestedList) {
this.values = [];
this.pos = 0;
const flatten = (list) => {
for (const ni of list) {
if (ni.isInteger()) this.values.push(ni.getInteger());
else flatten(ni.getList());
}
};
flatten(nestedList);
}
next() {
return this.values[this.pos++];
}
hasNext() {
return this.pos < this.values.length;
}
}2Optimal (lazy stack of cursors)
O(1) amortized per callEach integer and each list is pushed, inspected and popped once over the whole iteration, so the total work is O(N) spread across the N calls.O(D)The stack holds one cursor per nesting level, so D is the maximum depth; no copy of the integers is made.Keep a stack with one cursor (list + index) for every list you are currently inside. hasNext() advances until the top cursor points at an integer: an exhausted cursor is popped, a list element pushes a new cursor for that list. The integer it finds is cached, so repeated hasNext() calls do nothing extra and next() just hands it over. Only the part of the structure that is actually read gets visited.
- Constructor: push a cursor at index 0 of nestedList; no cached value.
- hasNext(): while nothing is cached and the stack is not empty: if the top cursor is past its list's end, pop it; otherwise take its element and advance the cursor. An integer is cached; a list gets a new cursor pushed.
- Return whether a value is cached.
- next(): call hasNext(), then return the cached value and clear the cache.
class NestedIterator implements Iterator<Integer> {
private final Deque<Iterator<NestedInteger>> stack = new ArrayDeque<>();
private Integer cached = null;
public NestedIterator(List<NestedInteger> nestedList) {
stack.push(nestedList.iterator());
}
@Override
public boolean hasNext() {
while (cached == null && !stack.isEmpty()) {
Iterator<NestedInteger> top = stack.peek();
if (!top.hasNext()) {
stack.pop();
continue;
}
NestedInteger ni = top.next();
if (ni.isInteger()) cached = ni.getInteger();
else stack.push(ni.getList().iterator());
}
return cached != null;
}
@Override
public Integer next() {
hasNext();
Integer v = cached;
cached = null;
return v;
}
}class NestedIterator:
def __init__(self, nestedList: List["NestedInteger"]):
self.stack = [[nestedList, 0]] # (list, index of the next element)
self.cached = None
def hasNext(self) -> bool:
while self.cached is None and self.stack:
top = self.stack[-1]
lst, i = top
if i == len(lst):
self.stack.pop()
continue
top[1] += 1
ni = lst[i]
if ni.isInteger():
self.cached = ni.getInteger()
else:
self.stack.append([ni.getList(), 0])
return self.cached is not None
def next(self) -> int:
self.hasNext()
v = self.cached
self.cached = None
return vclass NestedIterator {
vector<pair<const vector<NestedInteger>*, size_t>> stack; // (list, index of the next element)
bool has = false;
int cached = 0;
public:
NestedIterator(vector<NestedInteger>& nestedList) {
stack.push_back({&nestedList, 0});
}
bool hasNext() {
while (!has && !stack.empty()) {
auto& top = stack.back();
if (top.second == top.first->size()) {
stack.pop_back();
continue;
}
const NestedInteger& ni = (*top.first)[top.second++];
if (ni.isInteger()) {
cached = ni.getInteger();
has = true;
} else {
stack.push_back({&ni.getList(), 0});
}
}
return has;
}
int next() {
hasNext();
has = false;
return cached;
}
};class NestedIterator {
constructor(nestedList) {
this.stack = [[nestedList, 0]]; // (list, index of the next element)
this.cached = null;
}
hasNext() {
while (this.cached === null && this.stack.length > 0) {
const top = this.stack[this.stack.length - 1];
const [list, i] = top;
if (i === list.length) {
this.stack.pop();
continue;
}
top[1]++;
const ni = list[i];
if (ni.isInteger()) this.cached = ni.getInteger();
else this.stack.push([ni.getList(), 0]);
}
return this.cached !== null;
}
next() {
this.hasNext();
const v = this.cached;
this.cached = null;
return v;
}
}Edge cases to test
- Empty inner lists, including lists that contain only empty lists
- No integers anywhere: hasNext() is false from the start
- hasNext() called several times in a row without next()
- next() called without a preceding hasNext()
- Very deep nesting like [[[[5]]]]
Hints
Hint 1
The simplest correct iterator copies everything into a flat list in the constructor. What does that cost when only a few elements are read?
Hint 2
To be lazy, keep a stack of positions: one cursor per list you are currently inside.
Hint 3
Let hasNext() do the work: keep descending into lists and popping finished ones until the cursor on top points at an integer (or the stack is empty). Then next() just returns it.
FAQ
What is the best time complexity for Flatten Nested List Iterator?
Optimal (lazy stack of cursors) runs in O(1) amortized per call time and O(D) extra space. Each integer and each list is pushed, inspected and popped once over the whole iteration, so the total work is O(N) spread across the N calls.
Which pattern does Flatten Nested List Iterator use?
It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Min Stack, Design a Stack With Increment Operation, Maximum Frequency Stack.
Is there a brute force solution for Flatten Nested List Iterator?
Yes. Brute force (flatten everything up front) takes O(N) constructor, O(1) next/hasNext time and O(N) space. In the constructor, walk the whole structure recursively and copy every integer into one flat list.
Which edge cases should I test for Flatten Nested List Iterator?
Empty inner lists, including lists that contain only empty lists; No integers anywhere: hasNext() is false from the start; hasNext() called several times in a row without next(); next() called without a preceding hasNext(); Very deep nesting like [[[[5]]]].