Previous greater element
Given an array of distinct elements, find previous greater element for every element. If previous greater element does not exist, print -1.
Examples:
Input : arr[] = {10, 4, 2, 20, 40, 12, 30} Output : -1, 10, 4, -1, -1, 40, 40 Input : arr[] = {10, 20, 30, 40} Output : -1, -1, -1, -1 Input : arr[] = {40, 30, 20, 10} Output : -1, 40, 30, 20
Expected time complexity : O(n)
A simple solution is to run two nested loops. The outer loop picks an element one by one. The inner loop, find the previous element that is greater.
Implementation:
C++
// C++ program previous greater element // A naive solution to print previous greater // element for every element in an array. #include <bits/stdc++.h> using namespace std; void prevGreater( int arr[], int n) { // Previous greater for first element never // exists, so we print -1. cout << "-1, " ; // Let us process remaining elements. for ( int i = 1; i < n; i++) { // Find first element on left side // that is greater than arr[i]. int j; for (j = i-1; j >= 0; j--) { if (arr[i] < arr[j]) { cout << arr[j] << ", " ; break ; } } // If all elements on left are smaller. if (j == -1) cout << "-1, " ; } } // Driver code int main() { int arr[] = { 10, 4, 2, 20, 40, 12, 30 }; int n = sizeof (arr) / sizeof (arr[0]); prevGreater(arr, n); return 0; } |
Java
// Java program previous greater element // A naive solution to print // previous greater element // for every element in an array. import java.io.*; import java.util.*; import java.lang.*; class GFG { static void prevGreater( int arr[], int n) { // Previous greater for // first element never // exists, so we print -1. System.out.print( "-1, " ); // Let us process // remaining elements. for ( int i = 1 ; i < n; i++) { // Find first element on // left side that is // greater than arr[i]. int j; for (j = i- 1 ; j >= 0 ; j--) { if (arr[i] < arr[j]) { System.out.print(arr[j] + ", " ); break ; } } // If all elements on // left are smaller. if (j == - 1 ) System.out.print( "-1, " ); } } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 4 , 2 , 20 , 40 , 12 , 30 }; int n = arr.length; prevGreater(arr, n); } } |
Python 3
# Python 3 program previous greater element # A naive solution to print previous greater # element for every element in an array. def prevGreater(arr, n) : # Previous greater for first element never # exists, so we print -1. print ( "-1" ,end = ", " ) # Let us process remaining elements. for i in range ( 1 , n) : flag = 0 # Find first element on left side # that is greater than arr[i]. for j in range (i - 1 , - 1 , - 1 ) : if arr[i] < arr[j] : print (arr[j],end = ", " ) flag = 1 break # If all elements on left are smaller. if j = = 0 and flag = = 0 : print ( "-1" ,end = ", " ) # Driver code if __name__ = = "__main__" : arr = [ 10 , 4 , 2 , 20 , 40 , 12 , 30 ] n = len (arr) prevGreater(arr, n) # This code is contributed by ANKITRAI1 |
C#
// C# program previous greater element // A naive solution to print // previous greater element // for every element in an array. using System; class GFG { static void prevGreater( int [] arr, int n) { // Previous greater for // first element never // exists, so we print -1. Console.Write( "-1, " ); // Let us process // remaining elements. for ( int i = 1; i < n; i++) { // Find first element on // left side that is // greater than arr[i]. int j; for (j = i-1; j >= 0; j--) { if (arr[i] < arr[j]) { Console.Write(arr[j] + ", " ); break ; } } // If all elements on // left are smaller. if (j == -1) Console.Write( "-1, " ); } } // Driver Code public static void Main() { int [] arr = {10, 4, 2, 20, 40, 12, 30}; int n = arr.Length; prevGreater(arr, n); } } |
PHP
<?php // php program previous greater element // A naive solution to print previous greater // element for every element in an array. function prevGreater(& $arr , $n ) { // Previous greater for first element never // exists, so we print -1. echo ( "-1, " ); // Let us process remaining elements. for ( $i = 1; $i < $n ; $i ++) { // Find first element on left side // that is greater than arr[i]. for ( $j = $i -1; $j >= 0; $j --) { if ( $arr [ $i ] < $arr [ $j ]) { echo ( $arr [ $j ]); echo ( ", " ); break ; } } // If all elements on left are smaller. if ( $j == -1) echo ( "-1, " ); } } // Driver code $arr = array (10, 4, 2, 20, 40, 12, 30); $n = sizeof( $arr ) ; prevGreater( $arr , $n ); //This code is contributed by Shivi_Aggarwal. ?> |
Javascript
<script> // Javascript program previous greater element // A naive solution to print // previous greater element // for every element in an array. function prevGreater(arr,n) { // Previous greater for // first element never // exists, so we print -1. document.write( "-1, " ); // Let us process // remaining elements. for (let i = 1; i < n; i++) { // Find first element on // left side that is // greater than arr[i]. let j; for (j = i-1; j >= 0; j--) { if (arr[i] < arr[j]) { document.write(arr[j] + ", " ); break ; } } // If all elements on // left are smaller. if (j == -1) document.write( "-1, " ); } } // Driver Code let arr=[10, 4, 2, 20, 40, 12, 30]; let n = arr.length; prevGreater(arr, n); // This code is contributed by avanitrachhadiya2155 </script> |
Output
-1, 10, 4, -1, -1, 40, 40,
An efficient solution is to use stack data structure. If we take a closer look, we can notice that this problem is a variation of stock span problem. We maintain previous greater element in a stack.
C++
// C++ program previous greater element // An efficient solution to print previous greater // element for every element in an array. #include <bits/stdc++.h> using namespace std; void prevGreater( int arr[], int n) { // Create a stack and push index of first element // to it stack< int > s; s.push(arr[0]); // Previous greater for first element is always -1. cout << "-1, " ; // Traverse remaining elements for ( int i = 1; i < n; i++) { // Pop elements from stack while stack is not empty // and top of stack is smaller than arr[i]. We // always have elements in decreasing order in a // stack. while (s.empty() == false && s.top() < arr[i]) s.pop(); // If stack becomes empty, then no element is greater // on left side. Else top of stack is previous // greater. s.empty() ? cout << "-1, " : cout << s.top() << ", " ; s.push(arr[i]); } } // Driver code int main() { int arr[] = { 10, 4, 2, 20, 40, 12, 30 }; int n = sizeof (arr) / sizeof (arr[0]); prevGreater(arr, n); return 0; } |
Java
// Java program previous greater element // An efficient solution to // print previous greater // element for every element // in an array. import java.io.*; import java.util.*; import java.lang.*; class GFG { static void prevGreater( int arr[], int n) { // Create a stack and push // index of first element // to it Stack<Integer> s = new Stack<Integer>(); s.push(arr[ 0 ]); // Previous greater for // first element is always -1. System.out.print( "-1, " ); // Traverse remaining elements for ( int i = 1 ; i < n; i++) { // Pop elements from stack // while stack is not empty // and top of stack is smaller // than arr[i]. We always have // elements in decreasing order // in a stack. while (s.empty() == false && s.peek() < arr[i]) s.pop(); // If stack becomes empty, then // no element is greater on left // side. Else top of stack is // previous greater. if (s.empty() == true ) System.out.print( "-1, " ); else System.out.print(s.peek() + ", " ); s.push(arr[i]); } } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 4 , 2 , 20 , 40 , 12 , 30 }; int n = arr.length; prevGreater(arr, n); } } |
Python3
# Python3 program to print previous greater element # An efficient solution to print previous greater # element for every element in an array. import math as mt def prevGreater(arr, n): # Create a stack and push index of # first element to it s = list (); s.append(arr[ 0 ]) # Previous greater for first element # is always -1. print ( "-1, " , end = "") # Traverse remaining elements for i in range ( 1 , n): # Pop elements from stack while stack is # not empty and top of stack is smaller # than arr[i]. We always have elements in # decreasing order in a stack. while ( len (s) > 0 and s[ - 1 ] < arr[i]): s.pop() # If stack becomes empty, then no element # is greater on left side. Else top of stack # is previous greater. if len (s) = = 0 : print ( "-1, " , end = "") else : print (s[ - 1 ], ", " , end = "") s.append(arr[i]) # Driver code arr = [ 10 , 4 , 2 , 20 , 40 , 12 , 30 ] n = len (arr) prevGreater(arr, n) # This code is contributed by # mohit kumar 29 |
C#
// C# program previous greater element // An efficient solution to // print previous greater // element for every element // in an array. using System; using System.Collections.Generic; class GFG { static void prevGreater( int []arr, int n) { // Create a stack and push // index of first element // to it Stack< int > s = new Stack< int >(); s.Push(arr[0]); // Previous greater for // first element is always -1. Console.Write( "-1, " ); // Traverse remaining elements for ( int i = 1; i < n; i++) { // Pop elements from stack // while stack is not empty // and top of stack is smaller // than arr[i]. We always have // elements in decreasing order // in a stack. while (s.Count != 0 && s.Peek() < arr[i]) s.Pop(); // If stack becomes empty, then // no element is greater on left // side. Else top of stack is // previous greater. if (s.Count == 0) Console.Write( "-1, " ); else Console.Write(s.Peek() + ", " ); s.Push(arr[i]); } } // Driver Code public static void Main(String[] args) { int []arr = { 10, 4, 2, 20, 40, 12, 30 }; int n = arr.Length; prevGreater(arr, n); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program previous greater element // An efficient solution to // print previous greater // element for every element // in an array. function prevGreater(arr,n) { // Create a stack and push // index of first element // to it let s = []; s.push(arr[0]); // Previous greater for // first element is always -1. document.write( "-1, " ); // Traverse remaining elements for (let i = 1; i < n; i++) { // Pop elements from stack // while stack is not empty // and top of stack is smaller // than arr[i]. We always have // elements in decreasing order // in a stack. while (s.length!=0 && s[s.length-1] < arr[i]) s.pop(); // If stack becomes empty, then // no element is greater on left // side. Else top of stack is // previous greater. if (s.length==0) document.write( "-1, " ); else document.write(s[s.length-1] + ", " ); s.push(arr[i]); } } // Driver Code let arr=[10, 4, 2, 20, 40, 12, 30]; let n = arr.length; prevGreater(arr, n); // This code is contributed by rag2127 </script> |
Output
-1, 10, 4, -1, -1, 40, 40,
Complexity Analysis:
- Time Complexity: O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of array is added and removed from stack at most once. So there are total 2n operations at most. Assuming that a stack operation takes O(1) time, we can say that the time complexity is O(n).
- Auxiliary Space: O(n) in worst case when all elements are sorted in decreasing order.
Contact Us