Find the closest greater value for every element in the array

Optimal Approach: Solution using Sets

We can find the optimal solution to this problem using self-balancing BST (Implemented asset C++ and TreeSet Java). In a Self Balancing BST, we can do both insertions and closest greater operations, or I can say a binary search in O(log n) time. We initially store all elements in self-balancing BST and for every element, find the next greater element.

Algorithm

1. We have a given array, and we have to find the closest greater value for every element.
2. Create a set that initially stores all elements of the array.
3. Traverse through the whole array and for each element find closest greater element using Self-balancing BST.
4. Find the upper_bound of every element in the array.
5. Print the upper_bound every element.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
//closest greater value for every element
void closest_greater_value(int n, int arr[]){
  // n is size of array
 // intialising set
  set <int> set;  


  // insert every element in the Set


  for(int i=0; i<n; i++){
    set.insert(arr[i]);
  }
  
 // for every element find closest greater value
  for(int i=0; i<n; i++){
    // finding the upper bound of every element
     auto it = set.upper_bound(arr[i]);
     if( it == set.end() )
      cout<< -1 << “ “;
     else
       cout<< *it << “ “;
  }
}
//Driver function.
int main()
{
   int n= 6;  // size of array
   int arr[]={10, 5, 11, 6, 20, 12} ; // array intialising
   closest_greater_value(n,arr);
 }

You can also try this code with Online C++ Compiler

Run Code

Input-

6
10 5 11 6 20 12

Output-

11 6 12 10 -1 20

Complexity Analysis

The time complexity of this approach is- O(N log N), O(n) for traversing array, and for each element, we have to find O(log N) for upper bound and insertion in the Set.

The space complexity of this approach is- O(N) set leads to extra space

Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

1. Why are you using a set in this problem? 
   Ans- Because the Set does not contain any duplicate element, it requires less memory than the array data structure. The time complexity for insertion and finding the next greater element is O(log n).
2. What is the difference between ordered_set and unordered_set?
   Ans- Ordered_set using a red-black tree and unordered_set using the concept of hashing. Ordered stores the element in sorted order whereas unordered stores in random order.
3. What could be another approach if we don't use the Set here?
   Ans- We can use vector in Set and sort the array using merge sort in    O(n log n). Then by binary search, we find the next greater element for every element in log n.

Key takeaways

In this blog, we have learned how to find the closest greater value for an element in a given array of integers. 

We hope you have gained some insight to this problem, so it's now time to grab more and more concepts and start practicing more such problems on Code Studio.

The other topics that can be taken into consideration for further knowledge can be followed by using :

1. Left View Of Binary Tree

2. Bottom View of Binary Tree

Keep Learning, Keep Going.

Happy Coding!

You can learn more about the Set and practice similar problems on the Coding Ninjas Studio.