LeetCode Entry

341. Flatten Nested List Iterator

20.10.2023 medium 2023 kotlin

Implement graph iterator

341. Flatten Nested List Iterator medium blog post substack image.png

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 do pop on next()
  • it is better to advance after each next() call to know if there is a next position
  • careful with the order of elements when expanding

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


class NestedIterator(nestedList: List<NestedInteger>) : Stack<NestedInteger>() {
    init {
      addAll(nestedList.reversed())
      advance()
    }
    fun advance() {
      while (isNotEmpty() && !peek().isInteger()) {
        addAll(pop().list.reversed())
      }
    }
    fun next(): Int = pop().integer.also { advance() }
    fun hasNext(): Boolean = isNotEmpty()
}