Last Updated: 26 Dec, 2021
Next Greater Element - I
Moderate
Asked in companies
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.
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
Approaches
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 :
- Initialize an array ‘ans’, this array will store the next greater element for each element of array ‘A’.
- 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’.
- Search the current element in array ‘B’, once the element is found:
- Finally, return the array ‘ans’.
For each element in array ‘B’ if the element is less than N, then we can find its next greater element (NGE) and store it in an array or a hash-map.
To find the NGE’s, iterate the array ‘B’ and maintain a stack to store the indices. We push the current index into the stack if the stack is empty or the current element is less than or equal to the element whose index is on the top of the stack.
If the current element is greater than the element whose index is on the top then the NGE(next greater element) for the index on the top of the stack is the current element and we pop out that index from the stack, we keep repeating this till the stack remains non-empty and till the current element is greater, after that push the current index into the stack.
In the end, the indices that will remain in the stack will have their NGE’s as -1. This can be tackled by initializing all the elements as -1.
We now have all the information about NGE’s of each element from 0 to N - 1, we can simply traverse the array ‘A’, and look into the NGE’s calculated for each element of array ‘B’ to find the corresponding answer that is required.
The steps are as follows :
- Declare an array ‘nextGreater’ of size N, i’th entry in this array will correspond to the next greater element for the i’th value. Initialize all the values to -1.
- Initialize an array ‘ans’, this array will store the next greater element for each element of array ‘A’.
- Initialize a stack data structure ‘st’, this will store the next greater elements corresponding to elements in array ‘B’.
- Iterate all the elements in array ‘B’:
- Run a while loop still the stack is non-empty, inside this loop:
- Find the value ‘tp’ corresponding to the top index lying in the stack.
- If the top value ‘tp’ is less than B[i] and this value is less than N (an entry corresponding to this would lie in the array ‘A’) then update nextGreater[tp] with value B[i]. Else break the while loop.
- In case the stack was empty, then simply insert the current index into the stack.
- Run a while loop still the stack is non-empty, inside this loop:
- Finally, return the array ‘ans’.