Solution: Flatten Nested List Iterator

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 $1$ and $500$.
• The nested list consists of integers between $[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 process the nested list correctly, the elements need to be accessed in the order they appear in the original nested list.

The Has Next function performs a set of push and pop operations on the stack in the form of a loop. It checks if the top element of the stack is an integer. If so, it returns TRUE. Otherwise, if the top element is a list of integers, then it pops from the stack and pushes each element of the list in the stack in reverse order. This way, the lists at the top of the stack are converted into individual integers whenever the Has Next function is called. If the stack is empty, the function returns FALSE.

The Next function first calls the Has Next function to check if there is an integer in the stack. If the Has Next function returns TRUE, it pops from the stack and returns this popped value.

Here is an example of how this function works: