- Amazon, Arrays, Binary Search Tree, Competitive Programming, cpp-set, Hash, Tree

Print greater elements present on the left side of each array element

Print greater elements present on the left side of each array elementGiven 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: 59: 0: 9 5 316: 12: 16Input: arr[] = {1, 2, 0}Output:1: 2: 0: 2 1Naive 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.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:Below is the implementation of the above approach:C++#include using namespace std;  void printGreater(vector& arr){    int n = arr.size();              set s;          for (int i = 0; i < n; i++) {                          auto p = s.insert(arr[i]);        auto j = s.begin();          cout