# Find the closest greater value for every element in the array

## Introduction

This blog will learn to find the closest greater value for every element in the array. So let's suppose we have an array. We have to find the closest greater value for the element in the array.

For example-

``````Given Array- 2 5 3 4 20 9
After removing duplicates from the unsorted linked list- 3 9 4 5 -1 20``````

Explanation-

The closest greater value for 2 is 3

The closest greater value for 5 is 9

The closest greater value for 3 is 4

The closest greater value for 4 is 5

There is no greater value for 20, so we print -1

The closest greater value for 9 is 20

To find the closest greater value for every element in the array, we will start with the naive approach to use two loops. After that, we will discuss the optimized approach at the cost of some space.

## Naive Approach

In the naive approach to finding the closest greater value for every element, We have to use two nested loops. One is for indexing every element. The second loop is for finding the next greater element in the array.

### Algorithm

1. We have a given array, and we must find the closest greater value for every element.
2. Iterate through the array one by one for each index.
1. We have to find the closest greater value.
2. Iterate the whole array again and save the closest greater value from the array.
3. Print that saves value for 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
for(int i = 0; i<n ; i++) { // for traversing ever element

int closest_greater = -1; // intialise with -1
for(int j=0 ;j<n; j++) { // loop for finding closest greater value to arr[i]
//if we are on same index
if(i == j) continue;
// find any greater element to arr[i] then minimise its value
if(arr[j] > arr[i]){
if( closest_greater == -1)
closest_greater =  arr[j];
else
closest_greater=min(closest_greater,arr[j]);
}
}
cout<<closest_greater<<” “;
}
}
//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);
}``````

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(N2). We traverse via two nested loops for every element.

The space complexity of this approach is- O(1).

## 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);
}``````

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

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 :

Keep Learning, Keep Going.

Happy Coding! 