algoadvance

Leetcode 341. Flatten Nested List Iterator

Problem Statement

You are given a nested list of integers. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(vector<NestedInteger> &nestedList) initializes the iterator with the nested list nestedList.
• int next() returns the next integer in the nested list.
• bool hasNext() returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

The input nestedList is a list of NestedInteger objects.

Clarifying Questions

1. Can the nested list be empty?
   • Yes, the nested list can be empty.
2. Are the integers positive or can they include negative numbers and zero as well?
   • They can include negative numbers and zero as well.
3. What should be returned if the input list is empty?
   • If the input list is empty, hasNext() should return false immediately and next() should not be called.
4. Will next() be called only if hasNext() returns true?
   • Yes, it can be assumed that next() will be called only if hasNext() returns true.

Strategy

To solve this problem, you can use a stack to keep track of the nested lists and their current indices.

1. Initialize the stack with the given nestedList.
2. Flatten the list as you traverse it using the hasNext and next methods.
3. Use a helper function to handle the flattening of nested structures recursively.

Code

Below is the C++ implementation of the NestedIterator class:

#include <vector>
#include <stack>
using namespace std;

// This is the interface that allows for creating nested lists.
class NestedInteger {
public:
    // Return true if this NestedInteger holds a single integer, rather than a nested list.
    bool isInteger() const;
    
    // Return the single integer that this NestedInteger holds, if it holds a single integer.
    // The result is undefined if this NestedInteger holds a nested list.
    int getInteger() const;
    
    // Return the nested list that this NestedInteger holds, if it holds a nested list.
    // The result is undefined if this NestedInteger holds a single integer.
    const vector<NestedInteger> &getList() const;
};

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        flattenList(nestedList);
    }
    
    int next() {
        int value = flattenedList[idx];
        ++idx;
        return value;
    }
    
    bool hasNext() {
        return idx < flattenedList.size();
    }
    
private:
    vector<int> flattenedList;
    size_t idx = 0;
    
    void flattenList(const vector<NestedInteger> &nestedList) {
        for (const auto& ni : nestedList) {
            if (ni.isInteger()) {
                flattenedList.push_back(ni.getInteger());
            } else {
                flattenList(ni.getList());
            }
        }
    }
};

Time Complexity

• Constructor (NestedIterator): O(n), where n is the total number of integers in the nested list, because we traverse the entire list to flatten it initially.
• next() and hasNext(): Both are O(1), as we are just reading from a pre-flattened list and maintaining an index.

This approach ensures that the list is traversed once and all subsequent operations are efficient.

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?