Last updated on July 18th, 2024 at 03:44 am

Here, We see Flatten Nested List Iterator LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Design, Stack

Companies

Facebook, Google, Twitter

Level of Question

Medium

Flatten Nested List Iterator LeetCode Solution

Problem Statement

You are given a nested list of integers nestedList. 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(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 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

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:
Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

1. Flatten Nested List Iterator LeetCode Solution C++

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        begins.push(nestedList.begin());
        ends.push(nestedList.end());
    }
    int next() {
        hasNext();
        return (begins.top()++)->getInteger();
    }
    bool hasNext() {
        while (begins.size()) {
            if (begins.top() == ends.top()) {
                begins.pop();
                ends.pop();
            } else {
                auto x = begins.top();
                if (x->isInteger())
                    return true;
                begins.top()++;
                begins.push(x->getList().begin());
                ends.push(x->getList().end());
            }
        }
        return false;
    }

private:
    stack<vector<NestedInteger>::iterator> begins, ends;
};

2. Flatten Nested List Iterator LeetCode Solution Java

public class NestedIterator implements Iterator<Integer> {
    public NestedIterator(List<NestedInteger> nestedList) {
        lists = new Stack<>();
        lists.push(nestedList.listIterator());
    }
    public Integer next() {
        hasNext();
        return lists.peek().next().getInteger();
    }
    public boolean hasNext() {
        while (!lists.empty()) {
            if (!lists.peek().hasNext()) {
                lists.pop();
            } else {
                NestedInteger x = lists.peek().next();
                if (x.isInteger())
                    return lists.peek().previous() == x;
                lists.push(x.getList().listIterator());
            }
        }
        return false;
    }
    private Stack<ListIterator<NestedInteger>> lists;
}

3. Flatten Nested List Iterator Solution JavaScript

var NestedIterator = function(nestedList) {
    this.stack = [];
    this.beepboop(nestedList);
};

NestedIterator.prototype.beepboop = function(nestedList) {
    let n;
    while (n = nestedList.pop()) {
        if (n.isInteger()) this.stack.push(n.getInteger());
        else this.beepboop(n.getList());
    }
};

NestedIterator.prototype.hasNext = function() {
    return !!this.stack.length;
};

NestedIterator.prototype.next = function() {
	return this.stack.pop();
};

4. Flatten Nested List Iterator Solution Python

class NestedIterator(object):
    def __init__(self, nestedList):
        self.stack = [[nestedList, 0]]
    def next(self):
        self.hasNext()
        nestedList, i = self.stack[-1]
        self.stack[-1][1] += 1
        return nestedList[i].getInteger()  
    def hasNext(self):
        s = self.stack
        while s:
            nestedList, i = s[-1]
            if i == len(nestedList):
                s.pop()
            else:
                x = nestedList[i]
                if x.isInteger():
                    return True
                s[-1][1] += 1
                s.append([x.getList(), 0])
        return False