Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C#

Solution: Flatten Nested List Iterator

Explore how to implement a Nested Iterator class that flattens nested lists of integers using a stack. Understand how to manage the iteration with Next and Has Next functions, ensuring efficient traversal through deeply nested lists. This lesson helps you master stack operations and complexity considerations to solve this common coding interview challenge.

We'll cover the following...

Statement

You’re given a nested list of integers. Each element is either an integer or a list whose elements may also be integers or other integer lists. Your task is to implement an iterator to flatten the nested list.

You will have to implement the Nested Iterator class. This class has the following functions:

  • Constructor: This initializes the iterator with the nested list.
  • Next (): This returns the next integer in the nested list.
  • Has Next (): This returns TRUE if there are still some integers in the nested list. Otherwise, it returns FALSE.

Constraints

  • The nested list length is between 11 and 500500.
  • The nested list consists of integers between [1,104][1, 10^4].

Solution

We’ll use a stack to solve this problem. The stack will be used to store the integer and list of integers on the iterator object. We’ll push all the nested list data in the stack in reverse order in the constructor. The elements are pushed in reverse order because the iterator is implemented using a stack. In order to ...