Ninja And The List

Moderate
0/80
Average time to solve is 24m
profile
Contributed by
12 upvotes
Asked in companies
AmazonSalesforceVMware Software India Pvt Ltd

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]
Detailed explanation ( Input/output format, Notes, Images )
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
Hint

Can you iterate over the list?

Approaches (1)
Straight Forward 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 :  
 

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

// Preimplemented methods.
 

NestedIterator(vector<NestedInteger> &nestedList)

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

 

int next() 

  1. return answer[i++]

bool hasNext()

  1. return i < answer.size()

 

// Function to make the list flattered

void makeFlat(NestedInteger x)

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

O(N), Where 'N' is the size of the input list 'nestedList'

 

As we are iterating over the list 'nestedList' till it's end the time complexity will be O(N)

Space Complexity

O(N), Where 'N' is the size of the input list 'nestedList'

 

As we are using extra array 'answer' of size 'N' the space complexity will be O(N)

Code Solution
(100% EXP penalty)
Ninja And The List
Full screen
Console