Algorithm
Problem Name: 341. Flatten Nested List Iterator
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 listnestedList.int next()Returns the next integer in the nested list.boolean hasNext()Returnstrueif there are still some integers in the nested list andfalseotherwise.
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].
Constraints:
1 <= nestedList.length <= 500- The values of the integers in the nested list is in the range
[-106, 106].
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct NestedIterator {
int stack_sz;
int sp;
struct NestedInteger **stack;
int val;
};
#define PUSH(I, P) do { (I)->stack[(I)->sp ++] = (P); } while (0)
#define POP(I, P) do { (P) = (I)->stack[-- (I)->sp]; } while (0)
struct NestedIterator *nestedIterCreate(struct NestedInteger** nestedList, int nestedListSize) {
struct NestedIterator *iter;
struct NestedInteger **stack, *p;
int i, sz;
sz = nestedListSize + 100;
stack = malloc(sz * sizeof(struct NestedInteger *));
iter = malloc(sizeof(struct NestedIterator));
//assert(stack && iter);
iter->stack_sz = sz;
iter->stack = stack;
iter->sp = 0;
while (nestedListSize > 0) {
p = nestedList[-- nestedListSize];
if (p) PUSH(iter, p);
}
return iter;
}
bool nestedIterHasNext(struct NestedIterator *iter) {
struct NestedInteger **list;
struct NestedInteger *p;
int n;
while (iter->sp) {
POP(iter, p);
if (NestedIntegerIsInteger(p)) {
//PUSH(iter, p);
iter->val = NestedIntegerGetInteger(p);
return true;
}
n = NestedIntegerGetListSize(p);
if (iter->sp + n >= iter->stack_sz) {
iter->stack_sz += n;
iter->stack = realloc(iter->stack, iter->stack_sz * sizeof(struct NestedInteger *));
//assert(iter->stack);
}
list = NestedIntegerGetList(p);
while (n > 0) {
p = list[-- n];
if (p) PUSH(iter, p);
}
}
return false;
}
int nestedIterNext(struct NestedIterator *iter) {
//printf("%d,", iter->val);
return iter->val; // has next is always called prior
}
/** Deallocates memory previously allocated for the iterator */
void nestedIterFree(struct NestedIterator *iter) {
free(iter->stack);
free(iter);
}
Input
nestedList = [[1,1],2,[1,1]]
Output
[1,1,2,1,1]
#2 Code Example with C++ Programming
Code -
C++ Programming
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
this->nestedList = &nestedList;
}
int next() {
int n = q.front();
q.pop_front();
return n;
}
bool hasNext() {
while(q.empty() && i < nestedList->size()){
if((*nestedList)[i].isInteger())
q.push_back((*nestedList)[i].getInteger());
else{
NestedIterator* it = new NestedIterator((*nestedList)[i].getList());
while(it->hasNext()) q.push_back(it->next());
}
i++;
}
return !q.empty();
}
private:
vector < NestedInteger>* nestedList;
deque<int>q;
int i = 0;
};
Input
nestedList = [[1,1],2,[1,1]]
Output
[1,1,2,1,1]
#3 Code Example with Java Programming
Code -
Java Programming
public class NestedIterator implements Iterator {
private Stack stack;
public NestedIterator(List < NestedInteger> nestedList) {
this.stack = new Stack<>();
for (int i = nestedList.size() - 1; i >= 0; i--) {
this.stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
int value = this.stack.pop().getInteger();
return value;
}
@Override
public boolean hasNext() {
while (!this.stack.isEmpty() && !this.stack.peek().isInteger()) {
List < NestedInteger> ni = this.stack.pop().getList();
for (int i = ni.size() - 1; i >= 0; i--) {
this.stack.push(ni.get(i));
}
}
return !this.stack.isEmpty();
}
}
Input
nestedList = [1,[4,[6]]]
Output
[1,4,6]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
function flat(arr, res) {
for(let i = 0; i < arr.length; i++) {
if(arr[i].isInteger()) {
res.push(arr[i].getInteger())
} else {
flat(arr[i].getList() ,res)
}
}
}
const NestedIterator = function(nestedList) {
this.arr = []
this.idx = -1
flat(nestedList, this.arr)
};
NestedIterator.prototype.hasNext = function() {
return this.idx + 1 < this.arr.length
};
NestedIterator.prototype.next = function(> {
this.idx += 1
return this.arr[this.idx]
};
Input
nestedList = [1,[4,[6]]]
Output
[1,4,6]
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0341_FlattenNestedListIterator
{
private Stack < NestedInteger> stack;
public _0341_FlattenNestedListIterator(IList nestedList)
{
this.stack = new Stack();
for (int i = nestedList.Count - 1; i >= 0; i--)
stack.Push(nestedList[i]);
}
public bool HasNext()
{
while (stack.Count > 0 && !stack.Peek().IsInteger())
{
var ni = stack.Pop();
var list = ni.GetList();
for (int i = list.Count - 1; i >= 0; i--)
stack.Push(list[i]);
}
return stack.Count > 0;
}
public int Next()
{
if (!HasNext()) throw new IndexOutOfRangeException();
return stack.Pop().GetInteger();
}
public class NestedInteger
{
private int? number;
private IList < NestedInteger> list;
public NestedInteger()
{
number = null;
list = new List < NestedInteger>();
}
public NestedInteger(int value)
{
number = value;
list = new List < NestedInteger>();
}
public bool IsInteger()
{
return number.HasValue;
}
public int GetInteger()
{
return number.Value;
}
public void SetInteger(int value)
{
number = value;
list = null;
}
public void Add(NestedInteger ni)
{
number = null;
if (list == null)
list = new List < NestedInteger>() { ni };
else
list.Add(ni);
}
public IList < NestedInteger> GetList()
{
return list;
}
}
}
}
Input
nestedList = [[1,1],2,[1,1]]
Output
[1,1,2,1,1]