algoadvance

Leetcode 341. Flatten Nested List Iterator

Problem Statement

You are given a nested list of integers NestedInteger. Implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code should implement the Iterator interface in Java.

Clarifying Questions

1. Is the NestedInteger class provided?
   • Yes, the NestedInteger class is provided and you don’t need to implement it. The methods that it provides are:
     • boolean isInteger() - returns true if this NestedInteger holds a single integer.
     • Integer getInteger() - returns the single integer that this NestedInteger holds.
     • List<NestedInteger> getList() - returns the nested list that this NestedInteger holds.
2. Can the nested lists contain empty lists?
   • Yes, the nested lists can contain empty lists.
3. What should happen if the iterator is called for next when hasNext is false?
   • Normally, it should throw a NoSuchElementException or indicate error in some manner typical for iterators.

Strategy

1. Initialization:
   • Use a stack to keep track of the iterators over the nested lists. Each element of the stack will be an iterator over the current list being processed.
2. Flattening Process:
   • In the hasNext method, we need to ensure that the top of the stack contains the next integer to be returned. If the top of the stack points to a nested list, we need to drill down and push iterators for deeper lists onto the stack until we reach an integer or exhaust the list.
3. Next Element Retrieval:
   • In the next method, if hasNext confirms that there is an element, we return the integer pointed to by the top of the stack and advance the iterator.

Code

Here’s the implementation of the NestedIterator class:

import java.util.*;

public class NestedIterator implements Iterator<Integer> {
    private Stack<Iterator<NestedInteger>> stack;
    private Integer nextInt;

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

    @Override
    public Integer next() {
        if (hasNext()) {
            Integer res = nextInt;
            nextInt = null;
            return res;
        }
        return null; // Or throw NoSuchElementException
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (!stack.peek().hasNext()) {
                stack.pop();
            } else {
                NestedInteger curr = stack.peek().next();
                if (curr.isInteger()) {
                    nextInt = curr.getInteger();
                    return true;
                } else {
                    stack.push(curr.getList().iterator());
                }
            }
        }
        return false;
    }
}

class NestedInteger {
    // This is a sample implementation. You don't need to implement it.
    public boolean isInteger() {
        // Implementation provided by LeetCode
        return false;
    }
  
    public Integer getInteger() {
        // Implementation provided by LeetCode
        return null;
    }
  
    public List<NestedInteger> getList() {
        // Implementation provided by LeetCode
        return null;
    }
}

Time Complexity

• Next Operation (next): O(1) once hasNext confirms the presence of the next integer.
• Checking for Next (hasNext): Amortized O(1). In the worst case, it may have to delve through many nested lists, but each element is processed exactly once due to stack operations.

This implementation balances efficiency with clear stack-based processing to handle nested iterators effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?