_341. Flatten Nested List Iterator.md

341. Flatten Nested List Iterator

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 02, 2024

Last updated : July 02, 2024

---

Related Topics : Stack, Tree, Depth-First Search, Design, Queue, Iterator

Acceptance Rate : 64.84 %

---

I choose to use a private inner class in this instance since my approach does an initial parsing of the data to remove empty NestedIntegers (e.g. the test case of [[[]]]). By using an PIC, I can call that to host the data when I make recursive creations of this iterator, saving that overhead time of $n$ which could in a worst case situation could result in a $O(n^2)$ overhead for initialization costs alone.

Since what we're iterating through is a NestedInteger, I thought it would be most suiting to create an Iterator that is, like the data, nested. So, in the program, I keep a tab of any current nested iterators, using them to their fullest to DFS through the data.

---

Solutions

• m341.java

Java

m341.java

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    private List<NestedInteger> data;
    private dataManagement manager;
    public NestedIterator(List<NestedInteger> nestedList) {
        this.data = nestedList;


        // Parses data upon receiving it, recursively removing any
        // cases that are empty i.e. containing no integer values
        for (int i = data.size() - 1; i >= 0; i--) {
            if (isEmpty(data.get(i))) {
                data.remove(i);
            }
        }

        // Assigns a managing private inner class so that the 
        // recusive creations of "NestedIterators" don't revalidate
        // the data (checking and removing empty sub-NestedIntegers)
        this.manager = new dataManagement(nestedList);
    }

    private boolean isEmpty(NestedInteger curr) {
        if (curr == null) {
            return true;
        }
        if (curr.isInteger()) {
            return false;
        }
        for (int i = curr.getList().size() - 1; i >= 0; i--) {
            if (isEmpty(curr.getList().get(i))) {
                curr.getList().remove(i);
            }
        }
        return curr.getList().size() == 0;
    }

    @Override
    public Integer next() {
        return manager.next();
    }

    @Override
    public boolean hasNext() {
        return manager.hasNext();
    }

    private class dataManagement{
        private List<NestedInteger> data;
        private dataManagement curr;
        public dataManagement(List<NestedInteger> nestedList) {
            this.data = nestedList;
        }

        public Integer next() {
            if (curr != null) {
                Integer output = curr.next();
                if (!curr.hasNext()) {
                    curr = null;
                }
                return output;
            }

            if (data.get(0).isInteger()) {
                Integer output = data.get(0).getInteger();
                data.remove(0);
                return output;
            }

            curr = new dataManagement(data.get(0).getList());
            data.remove(0);
            return this.next();
        }

        public boolean hasNext() {
            if ((data.size() == 0) && (curr == null))
                return false;
            return true;
        }
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */