20.10.2023
341. Flatten Nested List Iterator medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/376
Problem TLDR
Implement graph iterator
Intuition
We need to save all the deep levels positions, so let’s use a Stack.
Approach
we can store
nextInt
integer in a separate variable, or just leave it in a Stack and dopop
onnext()
it is better to
advance
after eachnext()
call to know if there is a next positioncareful with the order of elements when expanding
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
class NestedIterator(nestedList: List<NestedInteger>) :
LinkedList<NestedInteger>(nestedList) {
fun next() = pop().integer
fun hasNext(): Boolean {
while (isNotEmpty() && !peek().isInteger())
for (ni in pop().list.asReversed()) addFirst(ni)
return isNotEmpty()
}
}