# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation.
class NestedInteger:
def isInteger(self) -> bool:
pass
def getInteger(self) -> int:
pass
def getList(self) -> ['NestedInteger']:
pass
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.stack = []
self._pushList(nestedList)
def _pushList(self, nestedList):
# push in reverse order so that we can pop from the end (stack)
for ni in reversed(nestedList):
self.stack.append(ni)
def next(self) -> int:
self.hasNext()
return self.stack.pop().getInteger()
def hasNext(self) -> bool:
while self.stack:
top = self.stack[-1]
if top.isInteger():
return True
self.stack.pop()
self._pushList(top.getList())
return False
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation.
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* int getInteger() const;
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* const vector<NestedInteger> &getList() const;
* };
*/
class NestedIterator {
stack<NestedInteger> stk;
public:
NestedIterator(vector<NestedInteger> &nestedList) {
pushList(nestedList);
}
void pushList(const vector<NestedInteger>& nestedList) {
for (auto it = nestedList.rbegin(); it != nestedList.rend(); ++it) {
stk.push(*it);
}
}
int next() {
hasNext();
int val = stk.top().getInteger();
stk.pop();
return val;
}
bool hasNext() {
while (!stk.empty()) {
NestedInteger &top = stk.top();
if (top.isInteger()) {
return true;
}
stk.pop();
pushList(top.getList());
}
return false;
}
};
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation.
* public interface NestedInteger {
* public boolean isInteger();
* public Integer getInteger();
* public List<NestedInteger> getList();
* }
*/
public class NestedIterator implements Iterator<Integer> {
private Deque<NestedInteger> stack = new LinkedList<>();
public NestedIterator(List<NestedInteger> nestedList) {
pushList(nestedList);
}
private void pushList(List<NestedInteger> nestedList) {
for (int i = nestedList.size() - 1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
hasNext();
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;
}
}
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation.
* function NestedInteger() {
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* // @return {boolean}
* this.isInteger = function() {...};
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // @return {integer}
* this.getInteger = function() {...};
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // @return {NestedInteger[]}
* this.getList = function() {...};
* };
*/
var NestedIterator = function(nestedList) {
this.stack = [];
this._pushList = function(list) {
for (let i = list.length - 1; i >= 0; i--) {
this.stack.push(list[i]);
}
}
this._pushList(nestedList);
};
NestedIterator.prototype.hasNext = function() {
while (this.stack.length > 0) {
let top = this.stack[this.stack.length - 1];
if (top.isInteger()) {
return true;
}
this.stack.pop();
this._pushList(top.getList());
}
return false;
};
NestedIterator.prototype.next = function() {
this.hasNext();
return this.stack.pop().getInteger();
};
The Flatten Nested List Iterator problem asks you to implement an iterator over a nested list of integers. Each element in the list is either an integer or another nested list (which can, recursively, contain more integers or lists). You are given an initial nested list, and you must design a class that:
next() method that returns the next integer in the nested structure.hasNext() method that returns True (or true) if there are still integers left to iterate over.The iterator should flatten the list on-the-fly, meaning you should not flatten the entire structure at initialization. You must not reuse or skip any elements, and each integer should be returned exactly once, in the order they appear in a left-to-right depth-first traversal of the nested structure.
At first glance, this problem looks like a tree traversal, since the nested lists can be arbitrarily deep. One obvious (but suboptimal) approach is to flatten the entire nested list into a single array at the start, and then just iterate over it. However, this uses extra memory and does not meet the requirement to flatten "on-the-fly".
To do this efficiently, we need a way to traverse the nested structure as we go, keeping track of our current position and only expanding lists when necessary. This is similar to using a stack for depth-first search (DFS) in trees. The challenge is to make hasNext() and next() both efficient and correct, even when the next integer is buried several levels deep in nested lists.
We can use a stack to keep track of where we are in the nested structure. Each item on the stack is a NestedInteger object. Here’s how the algorithm works:
nestedList onto the stack in reverse order (so the first element is on top).True (we have a next integer).hasNext() to ensure the top is an integer, then pop and return it.This method ensures that we only expand lists when needed, and always return the next integer in the correct order.
Why use a stack? Because stacks naturally support depth-first traversal. By pushing elements in reverse order, we ensure the leftmost elements are processed first.
Suppose the input is [[1,1],2,[1,1]]. Here’s how the iterator works:
[1,1], 2, [1,1] onto the stack (in reverse order).hasNext(): Top is [1,1] (a list). Pop it, push 1, 1 onto the stack.1 (an integer). hasNext() returns True.next(): Pop and return 1.1 (integer), then 2 (integer).[1,1] (list): Pop and push 1, 1.1, 1.
The iterator returns: 1, 1, 2, 1, 1.
Brute-force approach: Flatten the entire list at the start. Time: O(N), Space: O(N), where N is the total number of integers.
Optimized stack-based approach:
The solution is both time and space efficient, as it only expands lists as needed.
The Flatten Nested List Iterator problem is a classic example of using a stack to simulate recursive traversal in an iterative way. By pushing elements in reverse order and only expanding lists when needed, we ensure efficient, on-the-fly flattening of deeply nested structures. This approach is elegant because it is both time and space efficient, and it mirrors the logic of depth-first search in trees.