[SOLVED] Find the least greater element on the right

Issue

I am trying to solve an algorithm wherein I have to find the least greater element on the right of an array reference

For an instance in the below array
Input: [8, 58, 71, 18, 31, 32, 63, 92,
43, 3, 91, 93, 25, 80, 28]

The least greater element on the right for the first element 8 is 18, for the second element 58 is 63 & so on. I need help with the logic to solve the algorithm. I intend to first solve with with brute force with a complexity of O(n^2).

The code I’ve written till now is below

public class Tmp {

public static void main(String[] args) {

    int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 };
    int[] tmpArr = new int[arr.length];
    int pos = 0;
    int k=0;

    for (int i = 0; i < arr.length-1; i++) { 
        //int next = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            if ((arr[j] > arr[i])) {
             tmpArr[k]=arr[j]; // take all the values to the right of the element which are greater than it
             k++;
            }
        }

I’ve created the second array tmpArr to take all the values on the right of an element which are greater than an it. Probably sort that array then & take the first value. But that logic doesn’t seem ok to me.

Another solution can be

for (int i = 0; i < arr.length-1; i++) { 
    int leastGreater = ? //Don't know what to initialize with
            for (int j = i + 1; j < arr.length; j++) {
                if ((arr[j] > arr[i])) {
                   if(arr[j]<leastGreater){
                 leastGreater = arr[j];
                  }
                }
            }

Can anyone help with a simpler solution?

Solution

To solve it O(n log n) you may use TreeSet and go from right to left.

TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = ar.length - 1; i >= 0; --i) {
    set.higher(ar[i]); // what you need, may be null
    set.add(ar[i]);
}

Answered By – RiaD

Answer Checked By – Dawn Plyler (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *