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

Flatten Nested List Iterator

Explore how to implement a Nested Iterator class that flattens nested lists of integers. Learn to design next and hasNext methods using stack operations to handle nested structures efficiently.

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 200200.
  • The nested list consists of integers between [1,104][1, 10^4].

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Flatten Nested List Iterator

1.

What is the output if the following set of parameters are passed to the Constructor(), Next, and Has next() functions?

Constructor([3, [6, 7], 8])
Next()
Has Next()
Next()
Next()
A.

NULL

3

TRUE

6

7

B.

NULL

3

TRUE

[6, 7]

8

C.

NULL

3

TRUE

[6, 7, 8]

9

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: You need to figure out the solution of the Has Next () function only.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3

Try it yourself

Implement your solution in NestedIterator.java in the following coding playground. You’ll need the provided supporting code to implement your solution.

Java
usercode > NestedIterator.java
import java.util.*;
class NestedIterator {
    // NestedIterator constructor inializes the stack using the given nestedList list
    public NestedIterator(List<NestedInteger> nestedList) {
        // Write your code here
    }
    // hasNext() will return True if there are still some integers in the
    // stack (that has nested_list elements) and, otherwise, will return False.
    public boolean hasNext() {
        // Replace this placeholder return statement with your code
        return false;
    }
    // Check if there is still an integer in the stack
    public int next() {
        // Replace this placeholder return statement with your code
        return -1;
    }
    // ------ Please don't change the following function ----------
    // flattenList function is used for testing porpuses.
    // Your code will be tested using this function
    public static List<Integer> flattenList(NestedIterator obj){
        List<Integer> result = new ArrayList<Integer>();
        while (obj.hasNext()) {
            result.add(obj.next());
        }
        return result;
    }
}
Flatten Nested List Iterator