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?
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.
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.
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.
You are not required to print anything; it has already been taken care of. Just implement the function.
1 ≤ T ≤ 10
1 ≤ N ≤ M ≤ 500
0 ≤ A[i] < N
0 ≤ B[i] < M
Time limit: 1 sec
2
6
1 2 0 3 4 5
7
3 5 0 2 1 6 4
3
0 1 2
3
0 1 2
6 6 2 5 -1 6
1 2 -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’.
2
1
0
1
0
1
0
3
0 2 1
-1
2
For each element in array ‘A’ find its corresponding occurrence in array ‘B’ and simply check all the elements to the right of it.
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 :
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 ).
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 ).
All tags
Sort by
Interview problems
easy cpp
#include <bits/stdc++.h>
vector<int> nextGreaterElement(int n, vector<int> A, int m, vector<int> B) {
// Write your code here.
vector<int> ans;
for(int i=0;i<n;i++){
int max=A[i];
for(int j=0;j<m;j++){
if(B[j]==max){
for(int k=j;k<m;k++){
if(B[k]>max){
max=B[k];
break;
}
}
if(max==A[i]){
ans.push_back(-1);
} else {
ans.push_back(max);
}
break;
}
}
}
return ans;
}
Interview problems
Simple Understandable C++ code
#include <bits/stdc++.h>
vector<int> nextGreaterElement(int n, vector<int> A, int m, vector<int> B) {
// Write your code here.
vector <int> right(m,-1);//first greater element
unordered_map<int,int> mp;
vector<int> ans;
for(int i=0; i<m-1; i++)
{
int temp=B[i];
for(int j=i+1; j<m; j++)
{
if(B[j]>temp)
{
right[i]=B[j];
break;
}
}
}
for(int i=0; i<m; i++)
{
int temp1=B[i];
int temp2=right[i];
mp[temp1]=temp2;
}
for(int i=0; i<n; i++)
{
ans.push_back(mp[A[i]]);
}
return ans;
}
Interview problems
C++ easy solution using stack|| beats 100%
#include <bits/stdc++.h>
vector<int> nextGreaterElement(int n1, vector<int> nums1, int n2, vector<int> nums2) {
// Write your code here.
unordered_map<int, int> nextGreater;
stack<int> s;
// Iterate over nums2 to find the next greater element for each element
for (int num : nums2) {
while (!s.empty() && s.top() < num) {
nextGreater[s.top()] = num;
s.pop();
}
s.push(num);
}
// Handle elements in nums2 for which no greater element was found
while (!s.empty()) {
nextGreater[s.top()] = -1;
s.pop();
}
// Iterate over nums1 and populate the result using nextGreater map
vector<int> ans;
for (int num : nums1) {
ans.push_back(nextGreater[num]);
}
return ans;
}
Interview problems
Unordered Map Solution
#include <bits/stdc++.h>
vector<int> nextGreaterElement(int n, vector<int> A, int m, vector<int> B)
{
unordered_map <int,int> second;
for(int i=0;i<m;i++)
{
second[B[i]] = i;
}
vector<int> v(n);
for(int i=0;i<n;i++)
{
int idx = second[A[i]];
int ans=-1;
for(int k=idx;k<m;k++)
{
if(B[k] > A[i])
{
ans = B[k];
break;
}
}
v[i] = ans;
}
return v;
}
Interview problems
Easy O(N+M) solution using Stack - C++ [with comments]
#include <bits/stdc++.h>
vector<int> nextGreaterElement(int n, vector<int> A, int m, vector<int> B) {
// Write your code here.
stack <int> st;
unordered_map <int,int> ht;
// NGE for B and store the NGE for each element in hash table
for(int i=m-1;i>=0;i--){
while(!st.empty()){
if(st.top() > B[i]){
ht[B[i]] = st.top();
break;
}
st.pop();
}
if(st.empty())
ht[B[i]] = -1;
st.push(B[i]);
}
// Push NGE for every element from hash table
vector<int> ans;
for(auto e:A)
ans.push_back(ht[e]);
return ans;
}
Interview problems
JAVA CODE
Basic Approach is find the next greater element from the back of b array and also store the index of the element in b array. After that just traverse through the A array and check whether map contains the key or not if yess get the index and after that get the nextGreater element from that index.
Time Complexity: O(N+M) where N is the length of the A array and M is the length of the B array.
import java.util.* ;
import java.io.*;
public class Solution {
public static int[] nextGreaterElement(int n, int a[], int m2, int b[]) {
int[] ans=new int[a.length];
int[] nextGreater=new int[b.length];
Stack<Integer> s=new Stack<>();
HashMap<Integer,Integer> m=new HashMap<>();
for(int i=b.length-1;i>=0;i--){
while(!s.isEmpty() && s.peek()<=b[i]){
s.pop();
}
nextGreater[i]=s.isEmpty()?-1:s.peek();
s.push(b[i]);
m.put(b[i],i);
}
for(int i=0;i<a.length;i++){
if(m.containsKey(a[i])){
ans[i]=nextGreater[m.get(a[i])];
}else{
ans[i]=-1;
}
}
return ans;
}
}Interview problems
Discussion thread on Interview Problem | Next Greater Element - I
Hey everyone, creating this thread to discuss the interview problem - Next Greater Element - I.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Next Greater Element - I
