[LeetCode] 341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Thought process:
Use a stack. Iterate through the nested list from end to start.
  1. hasNext: because a NestedInteger can nest an empty list of NestedInteger, I cannot simply return true if the stack is not empty.
    1. If the stack is empty initially, return false.
    2. Peek the top element. Push its children reversely until the peeked element is an integer. If during this process the stack becomes empty (an empty list of NestedInteger), return false.
    3. Return true at the end.
  2. next: return top element from stack.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * // 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 null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    private Stack<NestedInteger> stack;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        pushListElements(nestedList);
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        if (stack.isEmpty()) {
            return false;
        }
        
        while (!stack.peek().isInteger()) {
            pushListElements(stack.pop().getList());
            if (stack.isEmpty()) {
                return false;
            }
        }
        return true;
    }
    
    private void pushListElements(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            stack.push(list.get(i));
        }
    }
}

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

Time complexity:
Say there are n nested integers, and they have an average depth of d. Constructor takes O(n). next() takes O(1). hasNext() takes O(d).

Comments

Popular posts from this blog

[LeetCode] 631. Design Excel Sum Formula

[LeetCode] 269. Alien Dictionary

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee