Peeking Iterator

Moderate

0/80

Average time to solve is 25m

Contributed by

1 upvote

Asked in companies

Problem statement

Implement the given PeekingIterator class consisting of four functions:

Peeking Iterator (int arr[]): Initialize the object with the given array element.

int next(): Returns the next element and moves the pointer to the next element.

bool hasNext(): Return true if there is still an element in the array that otherwise returns false.

int peek(): Return the next element in the array but don’t move the pointer to the next element.

You will be given ‘Q’ queries consisting of 'next', 'hasNext', and 'peek' operations. In each query input is of the following type:

0 ‘array/list’ - Initialize the object with the given array element.

1 - Return the next element and move the pointer to the next element.

2 - Return true if there are elements in the array, otherwise return false. 

3 - Perform a peek operation in the array.

For Example:

0 3 7 9 10
1
2 
3

Here we have 4 queries:
Firstly the query is of type 0. Sp, an object will be created with the list [7,9,10], and the pointer will be at 7.

Then the next query is 1 so we will return 7 and the pointer will move to 9.

Then the next query is 2 and there are elements in the array so we will return 'True'.

The last query is 3. So, we will just return 9 by not moving the pointer ahead.

Note:

Only the first query will be of type 0.

You can't directly access the array, instead, you will be given access to a separate iterator class.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer ‘Q’ denoting the number of queries to be answered.

In the next ‘Q’ lines, inputs are 0,1,2 or 3 as mentioned above.

Output Format:

For each test case, for all the calls of the query of type:

1: Return the next element
2: Return true or false 
3: Return element at the pointer position

Note for each call of query, the output is printed in a separate line.

Constraints:

1 <= T <= 5
1 <= size of arr <= 1000
1 <= arr[i] <= 1000
1 <= Q <= 1000
All queries are valid.

Time Limit: 1 second

Sample Input 1:

2
5
0 4 1 2 3 4
1
1
3
2
5
0 3 1 2 3
1
1
3
2

Sample Output 1:

-1
1
2
3
true
-1
1
2
3
true

Explanation For Sample Output 1:

Test Case 1:

Queries:
0 - object is initiated with the given array elements, [1,2,3,4].

1 - return 1, and move pointer to 2,  [1,2,3,4]

1 - return 2, and move pointer to 3 [1,2,3,4]

3 - return 3, but pointer stays at same position [1,2,3,4]

2 - return true, as elements are there.

Test Case 2:

Queries:
0 - object is initiated with given array elements [1,2,3]

1 - return 1, the pointer is moved to 2, [1,2,3]

1 - return 2, the pointer is moved to 3,[1,2,3]

3 - return 3, the pointer stays at the same position. [1,2,3]

2 - return true, as the current pointer is on element 3.

Sample Input 2:

2
3
0 5 6 8 9 10 0 
3
3
4
0 2 10 11
3
1
2

Sample Output 2:

-1
6
6
-1
10
10
true

Hint 1

Think of a data structure which can fit in this design problem. Use the given Iterator class to make a new PeekingIterator class.

Approaches (1)

Approach 1

Overriding the Functions

Try to implement dynamic array/linked list as it has two attributes with it one is the data field and the other is the pointer pointing to the next node which is all we need in this problem.
Initialize it with the given array.
Initialize a head pointer that points to the first node of List.
For the next() query, first, check if the current node we are at is the last node of the list or not. If it is not the last node of the list, we can shift to the next node by means of our iterator and return its data field.
For hasnext(), simply it can be checked if we currently point to the last node of the list or not which can tell if next() exists or not.
For peek simply return the data field of the current node you are pointing to.

Time Complexity

O(N), where ‘N’ is the size of the array/list.

Initializing list with input array takes O(N) time. All the other peek() , next(), hasNext() operations have O(1) time complexity.

Space Complexity

O(N), where 'N' is the size of the array/list.

We have created a list of size ‘N’.

(100% EXP penalty)

Peeking Iterator

Console