Last Updated: 19 Jan, 2022

Ninja And The List

Moderate

Asked in companies

Solve now

Problem statement

Ninja has given a nested list of integers nestedList of size 'N'. Each element is either an integer or a list whose elements may also be integers or other lists.

Ninjas have asked to implement the following methods of 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 task is to help the ninja to implement the above methods.

Your code will be tested with the following pseudocode:

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

You will get the correct answer verdict if the answer matches the expected flattened list.

EXAMPLE:

Input List: [[1, 1], 2, [1, 1]]
Output List: [1, 1, 2, 1, 1]

Input Format :

The first line contains 'T', the number of test cases.
For each test case, there will be only one line in the input containing integers and some nested lists.

Output format :

Print the second line containing the flattered nested list.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given class.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^5
0 <= Values of integers in the nested list <= 10^5
Time Limit: 1sec

Solve now

Approaches

01 Approach

Approach: In this approach, we will iterate over the list and make a function 'makeFlat' to flatten the given list. Also, we will make the function 'isInteger' to check if the current element is an integer or not. We will push it in the extra array 'answer' if it is an integer. If it is not an integer, will call 'makeFlat' function for it.

While iterating over the list we will call 'makeFlat' for it and then store integers in it in the extra array.

We will initialize the variable 'i' for remembering the list's current position, and for the 'next()' method, we will return 'answer[i++]'.

For the method 'hasNext()' we will return 'i < answer.size()'.

Algorithm :

Initialize the empty vector ‘answer’
Initialize the integer ‘i’ by 0.

// Preimplemented methods.

NestedIterator(vector<NestedInteger> &nestedList)

Iterate over the ‘nestedList’ with iterator ‘x’ and call ‘makeFlat(x)’

int next()

return answer[i++]

bool hasNext()

return i < answer.size()

// Function to make the list flattered

void makeFlat(NestedInteger x)

If x.isInteger() then push ‘x.getInteger()’ in ‘answer’.
Else iterate over the ‘x’getList()’ with iterator ‘y’ and call ‘makeFlat(y)’.

Solve now