There are two ways to implement a “flat nested list iterator”

This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the 341. flat nested list iterator on LeetCode, of medium difficulty.

Tag: “DFS”, “queue”, “stack”

Give you a nested list of integers. You can design an iterator that iterates through all integers in this list of integers.

Each item in the list is either an integer or another list. The elements of a list can also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]] output: [1,1,2,1,1] explanation: by calling next repeatedly until hasNext returns false, next should return elements in the order [1,1,2,1,1].Copy the code

Example 2:

Input: [1,[4,[6]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, next should return elements in the order of [1,4,6].Copy the code

DFS + queue

Since all elements are provided at initialization time, a naive approach is to handle them at initialization time.

Because of the nesting, it is easier to do this through DFS and put the elements on a queue.

Code:

public class NestedIterator implements Iterator<Integer> {

    Deque<Integer> queue = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        dfs(nestedList);
    }

    @Override
    public Integer next(a) {
        return hasNext() ? queue.pollFirst() : -1;
    }

    @Override
    public boolean hasNext(a) {
        return! queue.isEmpty(); }void dfs(List<NestedInteger> list) {
        for (NestedInteger item : list) {
            if (item.isInteger()) {
                queue.addLast(item.getInteger());
            } else{ dfs(item.getList()); }}}}Copy the code

• Time complexity: build iterator O(n)O(n)O(n), call next()next()next() next() with hasNext()hasNext()hasNext() with O(1)O(1)O(1) O(1)
• Space complexity: O(n)O(n)O(n)

Recursive + stack

As an alternative, we do not preprocess all elements.

Instead, all nestedintegers are placed on the stack in reverse order and expanded when needed.

Code:

public class NestedIterator implements Iterator<Integer> {

    Deque<NestedInteger> stack = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) { NestedInteger item = list.get(i); stack.addLast(item); }}@Override
    public Integer next(a) {
        return hasNext() ? stack.pollLast().getInteger() : -1;
    }

    @Override
    public boolean hasNext(a) {
        if (stack.isEmpty()) {
            return false;
        } else {
            NestedInteger item = stack.peekLast();
            if (item.isInteger()) {
                return true;
            } else {
                item = stack.pollLast();
                List<NestedInteger> list = item.getList();
                for (int i = list.size() - 1; i >= 0; i--) {
                    stack.addLast(list.get(i));
                }
                returnhasNext(); }}}}Copy the code

• Time complexity: The complexity of constructing iterators is O(n)O(n)O(n), hasNext()hasNext()hasNext() is amortized O(1)O(1)O(1) Next() next() Next() Next() Next() in strict order of iterator access (hasNext()hasNext()hasNext() next()next()next() next()next()))O(1)O(1), If defensive programming is in effect, it is amortized O(1)O(1)O(1)
• Space complexity: O(n)O(n)O(n)

The last

This is the 341st article in our “Brush through LeetCode” series. The series started on 2021/01/01, and there are 1916 questions in LeetCode by the start date. Some of them have locks, so we will finish all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.