Given an array arr[] consisting of N distinct integers, the task is to print for each array element, all the greater elements present on its left.
Examples:
Input: arr[] = {5, 3, 9, 0, 16, 12}
Output:
5:
3: 5
9:
0: 9 5 3
16:
12: 16Input: arr[] = {1, 2, 0}
Output:
1:
2:
0: 2 1
Naive Approach: The simplest approach to solve the problem is to traverse the array and for each array element, traverse all its preceding elements and print the ones that are greater than the current element.
C++
// C++ program for Naive approach#include <bits/stdc++.h>using namespace std;// Function to print all greater elements on the left of each array elementvoid printGreater(vector<int>& arr){ // store the size of array in variable n int n = arr.size(); for (int i = 0; i < n; i++) { // result is used to store elements which are greater than current element present left side of current element vector<int> result; // traversing all the elements which are left of current element arr[i] for (int j = i - 1; j >= 0; j--) { //checking whether arr[j] (left element) is greater than current element or not // if yes then insert the element to the result vector if (arr[j] > arr[i]) { result.push_back(arr[j]); } } cout << arr[i] << ": "; //printing all the elements present in result vector for (int k = 0; k < result.size(); k++) { cout << result[k] << " "; } cout << endl; }}//Driver Codeint main(){ vector<int> arr{5, 3, 9, 0, 16, 12}; printGreater(arr); return 0;} |
Java
// java program for Naive approachimport java.util.*;class GFG{ // Function to print all greater elements on the left of each array element static void printGreater(ArrayList<Integer> arr) { // store the size of array in variable n int n = arr.size(); for (int i = 0; i < n; i++) { // result is used to store elements which // are greater than current element present // left side of current element ArrayList<Integer> result = new ArrayList<Integer>(); // traversing all the elements which // are left of current element arr[i] for (int j = i - 1; j >= 0; j--) { // checking whether arr[j] (left element) is // greater than current element or not // if yes then insert the element to the result vector if (arr.get(j) > arr.get(i)) { result.add(arr.get(j)); } } System.out.print(arr.get(i) + ": "); // printing all the elements present in result vector for (int k = 0; k < result.size(); k++) { System.out.print(result.get(k) +" "); } System.out.println(); } } // Driver Code public static void main(String args[]) { ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(5, 3, 9, 0, 16, 12)); printGreater(arr); }}// This code is contributed by bgangwar59. |
Python3
# Python3 program for Naive approach# Function to print all greater # elements on the left of each# array elementdef printGreater(arr): # Store the size of array # in variable n n = len(arr) for i in range(n): # Result is used to store elements # which are greater than current # element present left side of # current element result = [] # Traversing all the elements # which are left of current # element arr[i] j = i - 1 while(j >= 0): # Checking whether arr[j] (left element) # is greater than current element or not # if yes then insert the element to the # result vector if (arr[j] > arr[i]): result.append(arr[j]) j -= 1 print(arr[i], end = ": ") # Printing all the elements present # in result vector for k in range(len(result)): print(result[k], end = " ") print("\n", end = "")# Driver Codeif __name__ == '__main__': arr = [ 5, 3, 9, 0, 16, 12 ] printGreater(arr)# This code is contributed by ipg2016107 |
C#
// C# program for Naive approachusing System;using System.Collections.Generic;class GFG { // Function to print all greater elements on the left of // each array element static void printGreater(int[] arr) { // store the size of array in variable n int n = arr.Length; for (int i = 0; i < n; i++) { // result is used to store elements which are // greater than current element present left // side of current element List<int> result = new List<int>(); // traversing all the elements which are left of // current element arr[i] for (int j = i - 1; j >= 0; j--) { // checking whether arr[j] (left element) is // greater than current element or not // if yes then insert the element to the // result vector if (arr[j] > arr[i]) { result.Add(arr[j]); } } Console.Write(arr[i] + ": "); // printing all the elements present in result // vector for (int k = 0; k < result.Count; k++) { Console.Write(result[k] + " "); } Console.WriteLine(); } } // Driver Code public static void Main() { int[] arr = { 5, 3, 9, 0, 16, 12 }; printGreater(arr); }}// This code is contributed by ukasp. |
Javascript
<script> // Javascript program for Naive approach // Function to print all greater elements on the left of // each array element function printGreater(arr) { // store the size of array in variable n let n = arr.length; for (let i = 0; i < n; i++) { // result is used to store elements which are // greater than current element present left // side of current element let result = []; // traversing all the elements which are left of // current element arr[i] for (let j = i - 1; j >= 0; j--) { // checking whether arr[j] (left element) is // greater than current element or not // if yes then insert the element to the // result vector if (arr[j] > arr[i]) { result.push(arr[j]); } } document.write(arr[i] + ": "); // printing all the elements present in result // vector for (let k = 0; k < result.length; k++) { document.write(result[k] + " "); } document.write("</br>"); } } let arr = [ 5, 3, 9, 0, 16, 12 ]; printGreater(arr); // This code is contributed by mukesh07.</script> |
Output
5: 3: 5 9: 0: 9 3 5 16: 12: 16
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to make use of a self-balancing Binary Search Trees. Set in C++ is implemented using self-balancing BSTs and can be used to solve this problem. Follow the steps to solve the problem:
- Initialize a Set s, that stores the elements in non-decreasing order.
- Traverse the array over the indices 0 to N – 1 and perform the following operations:
- Insert arr[i] into the set s.
- Iterate from the beginning of the Set till p and print the elements in the Set.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print all greater elements// on the left of each array elementvoid printGreater(vector<int>& arr){ int n = arr.size(); // Set to implement // self-balancing BSTs set<int, greater<int> > s; // Traverse the array for (int i = 0; i < n; i++) { // Insert the current // element into the set auto p = s.insert(arr[i]); auto j = s.begin(); cout << arr[i] << ": "; // Iterate through the set while (j != p.first) { // Print the element cout << *j << " "; j++; } cout << endl; }}// Driver Codeint main(){ vector<int> arr{ 5, 3, 9, 0, 16, 12 }; printGreater(arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to print all greater elements// on the left of each array elementstatic void printGreater(int arr[]){ int n = arr.length; // Set to implement // self-balancing BSTs TreeSet<Integer> s = new TreeSet<>( Collections.reverseOrder()); // Traverse the array for(int i = 0; i < n; i++) { // Insert the current // element into the set s.add(arr[i]); System.out.print(arr[i] + ": "); // Iterate through the set for(int v : s) { if (v == arr[i]) break; // Print the element System.out.print(v + " "); } System.out.println(); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 5, 3, 9, 0, 16, 12 }; printGreater(arr);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to print all greater elements# on the left of each array elementdef printGreater(arr): n = len(arr) # Set to implement # self-balancing BSTs s = set([]) # Traverse the array for i in range(n): # Insert the current # element into the set s.add(arr[i]) print(arr[i], ": ", sep = "", end = "") temp = list(s) temp.sort() temp.reverse() # Iterate through the set for v in range(len(temp)): if (temp[v] == arr[i]): break # Print the element print(temp[v], end = " ") print()arr = [5, 3, 9, 0, 16, 12]printGreater(arr)# This code is contributed by divyesh072019. |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to print all greater elements // on the left of each array element static void printGreater(int[] arr) { int n = arr.Length; // Set to implement // self-balancing BSTs HashSet<int> s = new HashSet<int>(); // Traverse the array for(int i = 0; i < n; i++) { // Insert the current // element into the set s.Add(arr[i]); Console.Write(arr[i] + ": "); List<int> temp = new List<int>(); // Iterate through the set foreach(int v in s) { temp.Add(v); } temp.Sort(); temp.Reverse(); // Iterate through the set for(int v = 0; v < temp.Count; v++) { if (temp[v] == arr[i]) { break; } // Print the element Console.Write(temp[v] + " "); } Console.WriteLine(); } } // Driver code static void Main() { int[] arr = { 5, 3, 9, 0, 16, 12 }; printGreater(arr); }}// This code is contributed by rameshtravel07. |
Javascript
<script>// JavaScript program for the above approach// Function to print all greater elements// on the left of each array elementfunction printGreater(arr){ let n = arr.length; // Set to implement // self-balancing BSTs let s = new Set(); // Traverse the array for(let i = 0; i < n; i++) { // Insert the current // element into the set s.add(arr[i]); document.write(arr[i] + ": "); let temp=Array.from(s).sort(function(a,b){return b-a;}); // Iterate through the set for(let v=0;v< temp.length;v++) { if (temp[v] == arr[i]) break; // Print the element document.write(temp[v] + " "); } document.write("<br>"); }}// Driver Codelet arr=[5, 3, 9, 0, 16, 12];printGreater(arr);// This code is contributed by avanitrachhadiya2155</script> |
Output
5: 3: 5 9: 0: 9 5 3 16: 12: 16
Time Complexity: O(N2log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
