Flatten Nested List Iterator

Head on over here to try the problem for yourself.

I spent way too long trying to figure out that they had already provided the NestedInteger interface XD. The solution is simply a recursion over the elements of nestedList.

Algorithm

The goal is to build an iterator over the provided nestedList. So we need to implement next() and hasNext() for the given nestedList. I approach this by converting the nestedList into an ArrayList. I defined a function called build() which converts nestedList, to an ArrayList. It iterates over every element in the nestedList and processes them as follows:

  1. if item.isInteger() then arr.add(item.getInteger())
  2. else recursively go through every element in the list.

Here is an example that illustrates the problem.

nestedList = [1,2,[3,4,[5,6],7],8]

As you can see, element 2 of nestedList contains integers and a list. So we must check each element recursively to build the required arraylist.

Code

public class NestedIterator implements Iterator<Integer> {
  ArrayList<Integer> arr;
  int index;

  public NestedIterator(List<NestedInteger> nestedList) {
    arr = new ArrayList<>();
    index = 0;

    for(NestedInteger item : nestedList) {
      build(arr);
    }
  }

  public void build(NestedInteger item) {
    // isInteger() and getInteger() are
    // part of the NestedInteger interface
    
    if(item.isInteger())
      arr.add(item.getInteger());
    else {
      for(NestedInteger element : item) {
        build(element);
      }
    }
  }

  @Override
  public Integer next() {
    return arr.get(index++);
  }

  @Override
  public boolean hasNext() {
    return index < arr.size();
  }
}