## 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)