Find next Smaller of next Greater in an array
Last Updated :
05 Apr, 2023
Given array of integer, find the next smaller of next greater element of every element in array.
Note : Elements for which no greater element exists or no smaller of greater element exist, print -1.
Examples:
Input : arr[] = {5, 1, 9, 2, 5, 1, 7}
Output: 2 2 -1 1 -1 -1 -1
Explanation :
Next Greater -> Right Smaller
5 -> 9 9 -> 2
1 -> 9 9 -> 2
9 -> -1 -1 -> -1
2 -> 5 5 -> 1
5 -> 7 7 -> -1
1 -> 7 7 -> -1
7 -> -1 -1 -> -1
Input : arr[] = {4, 8, 2, 1, 9, 5, 6, 3}
Output : 2 5 5 5 -1 3 -1 -1
A simple solution is to iterate through all elements. For every element, find the next greater element of current element and then find right smaller element for current next greater element.
Code-
C++
#include<bits/stdc++.h>
using namespace std;
void nextSmallerOfNextGreater(int arr[], int n)
{
vector<int> vec;
for(int i=0;i<n-1;i++){
int temp=arr[i];
int next=-1;
int ans=-1;
for(int j=i+1;j<n;j++){
if(arr[j]>temp){
next=j;
break;
}
}
if(next==-1){vec.push_back(-1);}
else{
for(int j=next+1;j<n;j++){
if(arr[j]<arr[next]){
ans=j;
break;
}
}
if(ans==-1){vec.push_back(-1);}
else{vec.push_back(arr[ans]);}
}
}
vec.push_back(-1);
for(auto x: vec){
cout<<x<<" ";
}
cout<<endl;
}
int main()
{
int arr[] = {5, 1, 9, 2, 5, 1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
nextSmallerOfNextGreater(arr, n);
return 0;
}
|
Java
import java.util.*;
public class Main {
static void nextSmallerOfNextGreater(int arr[], int n) {
ArrayList<Integer> vec = new ArrayList<Integer>();
for(int i = 0; i < n - 1; i++) {
int temp = arr[i];
int next = -1;
int ans = -1;
for(int j = i + 1; j < n; j++) {
if(arr[j] > temp) {
next = j;
break;
}
}
if(next == -1) {
vec.add(-1);
}
else {
for(int j = next + 1; j < n; j++) {
if(arr[j] < arr[next]) {
ans = j;
break;
}
}
if(ans == -1) {
vec.add(-1);
}
else {
vec.add(arr[ans]);
}
}
}
vec.add(-1);
for(int x : vec) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String[] args) {
int arr[] = {5, 1, 9, 2, 5, 1, 7};
int n = arr.length;
nextSmallerOfNextGreater(arr, n);
}
}
|
Python3
def nextSmallerOfNextGreater(arr, n):
vec = []
for i in range(n-1):
temp = arr[i]
next = -1
ans = -1
for j in range(i+1, n):
if arr[j] > temp:
next = j
break
if next == -1:
vec.append(-1)
else:
for j in range(next+1, n):
if arr[j] < arr[next]:
ans = j
break
if ans == -1:
vec.append(-1)
else:
vec.append(arr[ans])
vec.append(-1)
for x in vec:
print(x, end=" ")
print()
arr = [5, 1, 9, 2, 5, 1, 7]
n = len(arr)
nextSmallerOfNextGreater(arr, n)
|
C#
using System;
using System.Collections.Generic;
public class MainClass
{
static void nextSmallerOfNextGreater(int[] arr, int n)
{
List<int> vec = new List<int>();
for (int i = 0; i < n - 1; i++) {
int temp = arr[i];
int next = -1;
int ans = -1;
for (int j = i + 1; j < n; j++) {
if (arr[j] > temp) {
next = j;
break;
}
}
if (next == -1) {
vec.Add(-1);
}
else {
for (int j = next + 1; j < n; j++) {
if (arr[j] < arr[next]) {
ans = j;
break;
}
}
if (ans == -1) {
vec.Add(-1);
}
else {
vec.Add(arr[ans]);
}
}
}
vec.Add(-1);
foreach(var x in vec) { Console.Write(x + " "); }
Console.WriteLine();
}
public static void Main()
{
int[] arr = { 5, 1, 9, 2, 5, 1, 7 };
int n = arr.Length;
nextSmallerOfNextGreater(arr, n);
}
}
|
Javascript
function nextSmallerOfNextGreater(arr, n) {
let vec = [];
for (let i = 0; i < n - 1; i++) {
let temp = arr[i];
let next = -1;
let ans = -1;
for (let j = i + 1; j < n; j++) {
if (arr[j] > temp) {
next = j;
break;
}
}
if (next == -1) {
vec.push(-1);
} else {
for (let j = next + 1; j < n; j++) {
if (arr[j] < arr[next]) {
ans = j;
break;
}
}
if (ans == -1) {
vec.push(-1);
} else {
vec.push(arr[ans]);
}
}
}
vec.push(-1);
for (let x of vec) {
process.stdout.write(x + " ");
}
console.log();
}
let arr = [5, 1, 9, 2, 5, 1, 7];
let n = arr.length;
nextSmallerOfNextGreater(arr, n);
|
Time Complexity of this solution is O(n2).
Space Complexity: O(1)
An efficient solution takes O(n) time. Notice that it is the combination of Next greater element & next smaller element in array.
Let input array be 'arr[]' and size of array be 'n'
find next greatest element of every element
step 1 : Create an empty stack (S) in which we store the indexes
and NG[] that is user to store the indexes of NGE
of every element.
step 2 : Traverse the array in reverse order
where i goes from (n-1 to 0)
a) While S is non empty and the top element of
S is smaller than or equal to 'arr[i]':
pop S
b) If S is empty
arr[i] has no greater element
NG[i] = -1
c) else we have next greater element
NG[i] = S.top() // here we store the index of NGE
d) push current element index in stack
S.push(i)
Find Right smaller element of every element
step 3 : create an array RS[] used to store the index of
right smallest element
step 4 : we repeat step (1 & 2) with little bit of
modification in step 1 & 2 .
they are :
a). we use RS[] in place of NG[].
b). In step (2.a)
we pop element form stack S while S is not
empty or the top element of S is greater than
or equal to 'arr[i]'
step 5 : compute all RSE of NGE :
where i goes from 0 to n-1
if NG[ i ] != -1 && RS[ NG [ i]] ! =-1
print arr[RS[NG[i]]]
else
print -1
Below is the implementation of above idea
C++
#include<bits/stdc++.h>
using namespace std;
void nextGreater(int arr[], int n, int next[], char order)
{
stack<int> S;
for (int i=n-1; i>=0; i--)
{
while (!S.empty() &&
((order=='G')? arr[S.top()] <= arr[i]:
arr[S.top()] >= arr[i]))
S.pop();
if (!S.empty())
next[i] = S.top();
else
next[i] = -1;
S.push(i);
}
}
void nextSmallerOfNextGreater(int arr[], int n)
{
int NG[n];
int RS[n];
nextGreater(arr, n, NG, 'G');
nextGreater(arr, n, RS, 'S');
for (int i=0; i< n; i++)
{
if (NG[i] != -1 && RS[NG[i]] != -1)
cout << arr[RS[NG[i]]] << " ";
else
cout<<"-1"<<" ";
}
}
int main()
{
int arr[] = {5, 1, 9, 2, 5, 1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
nextSmallerOfNextGreater(arr, n);
return 0;
}
|
Java
import java.util.Stack;
public class Main {
public static void nextGreater(int arr[], int next[], char order)
{
Stack<Integer> stack=new Stack<>();
for (int i=arr.length-1; i>=0; i--)
{
while (!stack.isEmpty() && ((order=='G')? arr[stack.peek()] <= arr[i]:arr[stack.peek()] >= arr[i]))
stack.pop();
if (!stack.isEmpty())
next[i] = stack.peek();
else
next[i] = -1;
stack.push(i);
}
}
public static void nextSmallerOfNextGreater(int arr[])
{
int NG[]=new int[arr.length];
int RS[]=new int[arr.length];
nextGreater(arr, NG, 'G');
nextGreater(arr, RS, 'S');
for (int i=0; i< arr.length; i++)
{
if (NG[i] != -1 && RS[NG[i]] != -1)
System.out.print(arr[RS[NG[i]]]+" ");
else
System.out.print("-1 ");
}
}
public static void main(String args[]) {
int arr[] = {5, 1, 9, 2, 5, 1, 7};
nextSmallerOfNextGreater(arr);
}
}
|
Python 3
def nextGreater(arr, n, next, order):
S = []
for i in range(n-1,-1,-1):
while (S!=[] and (arr[S[len(S)-1]] <= arr[i]
if (order=='G') else arr[S[len(S)-1]] >= arr[i] )):
S.pop()
if (S!=[]):
next[i] = S[len(S)-1]
else:
next[i] = -1
S.append(i)
def nextSmallerOfNextGreater(arr, n):
NG = [None]*n
RS = [None]*n
nextGreater(arr, n, NG, 'G')
nextGreater(arr, n, RS, 'S')
for i in range(n):
if (NG[i] != -1 and RS[NG[i]] != -1):
print(arr[RS[NG[i]]],end=" ")
else:
print("-1",end=" ")
if __name__=="__main__":
arr = [5, 1, 9, 2, 5, 1, 7]
n = len(arr)
nextSmallerOfNextGreater(arr, n)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public static void nextGreater(int []arr, int []next, char order)
{
Stack<int> stack=new Stack<int>();
for (int i=arr.Length-1; i>=0; i--)
{
while (stack.Count!=0 && ((order=='G')? arr[stack.Peek()] <= arr[i]:arr[stack.Peek()] >= arr[i]))
stack.Pop();
if (stack.Count!=0)
next[i] = stack.Peek();
else
next[i] = -1;
stack.Push(i);
}
}
public static void nextSmallerOfNextGreater(int []arr)
{
int []NG=new int[arr.Length];
int []RS=new int[arr.Length];
nextGreater(arr, NG, 'G');
nextGreater(arr, RS, 'S');
for (int i=0; i< arr.Length; i++)
{
if (NG[i] != -1 && RS[NG[i]] != -1)
Console.Write(arr[RS[NG[i]]]+" ");
else
Console.Write("-1 ");
}
}
public static void Main() {
int []arr = {5, 1, 9, 2, 5, 1, 7};
nextSmallerOfNextGreater(arr);
}
}
|
Javascript
<script>
function nextGreater(arr,next,order)
{
let stack = [];
for (let i = arr.length - 1; i >= 0; i--)
{
while (stack.length!=0 && ((order=='G')? arr[stack[stack.length-1]] <= arr[i] : arr[stack[stack.length-1]] >= arr[i]))
stack.pop();
if (stack.length != 0)
next[i] = stack[stack.length - 1];
else
next[i] = -1;
stack.push(i);
}
}
function nextSmallerOfNextGreater(arr)
{
let NG = new Array(arr.length);
let RS = new Array(arr.length);
for(let i = 0; i < arr.length; i++)
{
NG[i] = 0;
RS[i] = 0;
}
nextGreater(arr, NG, 'G');
nextGreater(arr, RS, 'S');
for (let i = 0; i < arr.length; i++)
{
if (NG[i] != -1 && RS[NG[i]] != -1)
document.write(arr[RS[NG[i]]] + " ");
else
document.write("-1 ");
}
}
let arr = [5, 1, 9, 2, 5, 1, 7];
nextSmallerOfNextGreater(arr);
</script>
|
Time complexity : O(n), where n is the size of the given array.
Auxiliary Space: O(n), where n is the size of the given array.
Please Login to comment...