Find the closest greater value for every element in the array

Ayush Tiwari
Last Updated: May 13, 2022

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

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 CodeStudio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think