# Solution For Flatten Nested List Iterator

Problem Description:
Implement an iterator to flatten a 2D vector. The vector consists of several nested vectors. Each nested vector can have any number of elements. The iterator should be able to work on any number of nested vectors.

Example:
Input:
[[1,1],2,[1,1]]

Output:
[1,1,2,1,1]

Note:
The input can be of any level of nesting.

Solution:
An easy approach to solve the problem is to flatten the input list when initializing the iterator. In this way, we can simply work with a one-dimensional list and iterate over it without the need for nested loops. Here is the code for the iterator class:

class NestedIterator:
def init(self, nestedList: [NestedInteger]):
self.data = [] self.flatten(nestedList)

``````def flatten(self, nestedList):
for elem in nestedList:
if elem.isInteger():
self.data.append(elem.getInteger())
else:
self.flatten(elem.getList())

def next(self) -> int:
return self.data.pop(0)

def hasNext(self) -> bool:
return len(self.data) > 0
``````

In the init method, we first initialize an empty list called self.data. Then, we call a helper function flatten that takes a nestedList as input and extracts all integers from it. We iterate over each item in the list and check if it is an integer or a nested list. If it is an integer, we append it to the self.data list. If it is a nested list, we call the flatten function recursively.

The next method simply returns the first item from the self.data list and removes it. The hasNext method checks whether the self.data list is empty or not. If it is empty, it returns False, otherwise returns True.

Sample Input:
nestedList = [1,[4,[6]]]

Sample Output:
iterator = NestedIterator(nestedList)
print(iterator.next()) # 1
print(iterator.next()) # 4
print(iterator.next()) # 6
print(iterator.hasNext()) # False

Explanation:
Here, we have a nestedList that has two nested lists inside it. We initialize a new iterator using the NestedIterator class, passing the nestedList as an argument.
The output shows that the iterator returns the values in the flattened form of the input list. The hasNext method returns False when all the elements are iterated over.

## Step by Step Implementation For Flatten Nested List Iterator

```/**
* // 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 getList();
* }
*/
public class NestedIterator implements Iterator {

// Use a stack to store all the NestedInteger
Stack stack;

public NestedIterator(List nestedList) {
stack = new Stack<>();
// Add all the element to the stack
for(NestedInteger ni: nestedList) {
stack.push(ni);
}
}

@Override
public Integer next() {
// Check if the stack is empty
if(stack.isEmpty()) {
return null;
}
// Peek the top element in the stack
NestedInteger curr = stack.peek();
// If the top element is an integer, pop it out and return it
if(curr.isInteger()) {
return stack.pop().getInteger();
}
// If the top element is a list
// Get the list and store it in a new stack
Stack tempStack = new Stack<>();
while(!curr.isInteger()) {
List list = curr.getList();
stack.pop();
// Add all the element in the list to the new stack
for(int i = list.size() - 1; i >= 0; i--) {
tempStack.push(list.get(i));
}
// Check if the new stack is empty
if(!tempStack.isEmpty()) {
curr = tempStack.peek();
}
}
// Add all the element in the new stack to the original stack
while(!tempStack.isEmpty()) {
stack.push(tempStack.pop());
}
// Return the integer
return curr.getInteger();
}

@Override
public boolean hasNext() {
// Check if the stack is empty
if(stack.isEmpty()) {
return false;
}
// Peek the top element in the stack
NestedInteger curr = stack.peek();
// If the top element is an integer, return true
if(curr.isInteger()) {
return true;
}
// If the top element is a list
// Get the list and store it in a new stack
Stack tempStack = new Stack<>();
while(!curr.isInteger()) {
List list = curr.getList();
stack.pop();
// Add all the element in the list to the new stack
for(int i = list.size() - 1; i >= 0; i--) {
tempStack.push(list.get(i));
}
// Check if the new stack is empty
if(!tempStack.isEmpty()) {
curr = tempStack.peek();
}
}
// Add all the element in the new stack to the original stack
while(!tempStack.isEmpty()) {
stack.push(tempStack.pop());
}
// Return true if the curr is an integer, false otherwise
return curr.isInteger();
}
}

/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/```
```# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
#
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class NestedIterator(object):

def __init__(self, nestedList):
"""
:type nestedList: List[NestedInteger]
"""
self.stack = nestedList[::-1]

def next(self):
"""
:rtype: int
"""
return self.stack.pop().getInteger()

def hasNext(self):
"""
:rtype: bool
"""
while self.stack:
top = self.stack[-1]
if top.isInteger():
return True
self.stack = self.stack[:-1] + top.getList()[::-1]
return False```
```/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
*     Return true if this NestedInteger holds a single integer, rather than a nested list.
*     @return {boolean}
*     this.isInteger = function() {
*         ...
*     };
*
*     Return the single integer that this NestedInteger holds, if it holds a single integer
*     Return null if this NestedInteger holds a nested list
*     @return {integer}
*     this.getInteger = function() {
*         ...
*     };
*
*     Return the nested list that this NestedInteger holds, if it holds a nested list
*     Return null if this NestedInteger holds a single integer
*     @return {NestedInteger[]}
*     this.getList = function() {
*         ...
*     };
* };
*/
/**
* @constructor
* @param {NestedInteger[]} nestedList
*/
var NestedIterator = function(nestedList) {

};

/**
* @this NestedIterator
* @returns {boolean}
*/
NestedIterator.prototype.hasNext = function() {

};

/**
* @this NestedIterator
* @returns {integer}
*/
NestedIterator.prototype.next = function() {

};

/**
* Your NestedIterator will be called like this:
* var i = new NestedIterator(nestedList), a = [];
* while (i.hasNext()) a.push(i.next());
*/```
```/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
*   public:
*     // Constructor initializes an empty nested list.
*     NestedInteger();
*
*     // Constructor initializes a single integer.
*     NestedInteger(int value);
*
*     // 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;
*
*     // Set this NestedInteger to hold a single integer.
*     void setInteger(int value);
*
*     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
*
*     // 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 &getList() const;
* };
*/
class NestedIterator {
public:
NestedIterator(vector &nestedList) {
// Initialize your data structure here.
for(int i = nestedList.size() - 1; i >= 0; --i) {
s.push(nestedList[i]);
}
}

// @return {int} the next element in the iteration
int next() {
NestedInteger t = s.top();
s.pop();
return t.getInteger();
}

// @return {boolean} true if the iteration has more element or false
bool hasNext() {
while(!s.empty()) {
NestedInteger t = s.top();
if(t.isInteger()) return true;
s.pop();
for(int i = t.getList().size() - 1; i >= 0; --i) {
s.push(t.getList()[i]);
}
}
return false;
}

private:
//@NOTE: This is a stack to store the next element
stack s;
};

/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) v.push_back(i.next());
*/```
```public class NestedIterator {

Stack stack;

public NestedIterator(List nestedList) {

stack = new Stack<>();

for(int i = nestedList.size() - 1; i >= 0; i--) {

stack.push(nestedList.get(i));

}

}

// @return {int} the next element in the iteration

public int next() {

return stack.pop().getInteger();

}

// @return {boolean} true if the iteration has more element or false

public boolean hasNext() {

while(!stack.isEmpty()) {

NestedInteger curr = stack.peek();

if(curr.isInteger()) {

return true;

}

stack.pop();

for(int i = curr.getList().size() - 1; i >= 0; i--) {

stack.push(curr.getList().get(i));

}

}

return false;

}

}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]