Next Greater Element - I

Moderate
0/80
profile
Contributed by
12 upvotes
Asked in companies
Expedia GroupAdobeAmazon

Problem statement

You are given an array ‘A’ containing a permutation ‘N’ numbers (0 ≤ A[i] < N). You are also given another array ‘B’ containing a permutation ‘M’ numbers (0 ≤ B[j] < M) and it is also given that N ≤ M.

For each element in array ‘A’ you need to find the first greater element to the right of the element in array ‘B’ that has the same value as the current array A’s element. In other words, for each ‘i’ from 0 to N - 1 in array ‘A’, you need to find an index ‘j’ in array ‘B’ such that A[i] = B[j], now you need to print the element that lies on the right of the j’th index and is also greater than B[j]. Print -1 if there is no greater element.

Follow Up : 
Can you solve it in O(N+M) time?
For Example : 
If ‘N’ = 6, ‘A’ = {1, 2, 0, 3, 4, 5}, ‘M’ = 7 and ‘B’ = {3, 5, 0, 2, 1, 6, 4}.

Then, we will return {6, 6, 2, 5, -1, 6} because:
For i = 0, A[i] = 1 and the first element greater than 1 that lies to the right of it in array ‘B’ is 6.
For i = 1, A[i] = 2 and the first element greater than 2 that lies to the right of it in array ‘B’ is 6.
For i = 2, A[i] = 0 and the first element greater than 0 that lies to the right of it in array ‘B’ is 2.
For i = 3, A[i] = 3 and the first element greater than 3 that lies to the right of it in array ‘B’ is 5.
For i = 4, A[i] = 4 and there is no greater element to the right of 4 in array ‘B’.
For i = 5, A[i] = 5 and the first element greater than 5 that lies to the right of it in array ‘B’ is 6.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the size of the array ‘A’.

The second line of each test case contains N space-separated integers ‘A’, denoting the array elements.


The third line of each test case contains a single integer ‘M’, denoting the size of the array ‘B’.

The fourth line of each test case contains M space-separated integers ‘B’, denoting the array elements.
Output Format : 
For each test case, for each element of array ‘A’, print its corresponding next greater element lying in array ‘B’.

Output for each test case will be printed on a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ N ≤ M ≤ 500
0 ≤ A[i] < N
0 ≤ B[i] < M

Time limit: 1 sec
Sample Input 1 :
2
6
1 2 0 3 4 5
7
3 5 0 2 1 6 4
3
0 1 2
3
0 1 2
Sample Output 1 :
6 6 2 5 -1 6
1 2 -1
Explanation For Sample Input 1 :
For test case 1 :
We will print {6, 6, 2, 5, -1, 6} because:
For i = 0, A[i] = 1 and the first element greater than 1 that lies to the right of it in array ‘B’ is 6.
For i = 1, A[i] = 2 and the first element greater than 2 that lies to the right of it in array ‘B’ is 6.
For i = 2, A[i] = 0 and the first element greater than 0 that lies to the right of it in array ‘B’ is 2.
For i = 3, A[i] = 3 and the first element greater than 3 that lies to the right of it in array ‘B’ is 5.
For i = 4, A[i] = 4 and there is no greater element to the right of 4 in array ‘B’.
For i = 5, A[i] = 5 and the first element greater than 5 that lies to the right of it in array ‘B’ is 6.

For test case 2 : 
We will print {1, 2, -1} because:
For i = 0, A[i] = 0 and the first element greater than 0 that lies to the right of it in array ‘B’ is 1.
For i = 1, A[i] = 1 and the first element greater than 1 that lies to the right of it in array ‘B’ is 2.
For i = 2, A[i] = 2 and there is no greater element to the right of 2 in array ‘B’.
Sample Input 2 :
2
1
0
1
0
1
0
3
0 2 1
Sample Output 2 :
-1
2
Hint

For each element in array ‘A’ find its corresponding occurrence in array ‘B’ and simply check all the elements to the right of it.

Approaches (2)
Brute Force

A simple brute force method to solve this question is to iterate all the elements of array ‘A’, and for each element, we will find the index at which that element occurs in array ‘B’ (the answer will always exist as N ≤ M). Once the index is found we can check all the indices to the right and stop searching when we find a greater element.

 

The steps are as follows :

  1. Initialize an array ‘ans’, this array will store the next greater element for each element of array ‘A’.
  2. Iterate all the elements in array ‘A’.
    • Search the current element in array ‘B’, once the element is found:
      • Check all the elements to the right, if a greater element is found then insert it in ‘ans’ and repeat the process for the next element in ‘A’. In case no greater element is found on the right, then insert -1 in ‘A’.
  3. Finally, return the array ‘ans’.
Time Complexity

O( N * M ), where N and M denote the size of the arrays.

 

In the worst case, for each element of array ‘A’ we might end up traversing all the elements of array ‘B’.

Hence the time complexity is O( N*M ).

Space Complexity

O( 1 )

 

No extra space is used to calculate the answer, we just use extra space to store the answer calculated.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Next Greater Element - I
Full screen
Console