Find the Next Greatest Element

Given an array, print the Next Greater Element (NGE) for every element. The Next Greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Examples:

• For any array, rightmost element always has next greater element as -1.

• For an array which is sorted in decreasing order, all elements have next greater element as -1.

-
For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows:

Element       NGE
       4      -->   5
       5      -->   25
       2      -->   25
       25     -->   -1

-
For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.

Element          NGE
      13      -->     -1
      7       -->     12
      6       -->     12
      12      -->     -1

```
final class DataSet {

private final int x;
private final int nextX;

public DataSet(int x, int nextX) {
this.x = x;
this.nextX = nextX;
}

public int getX() {
return x;
}

public int getNextX() {
return nextX;
}

@Override
public String toString() {
return "x: " + x + " nextX: " + nextX;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + nextX;
result = prime * result + x;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DataSet other = (DataSet) obj;
if (nextX != other.nextX)
return false;
if (x != other.x)
return false;
return true;
}
}

public final class NextGreatestElement {

private NextGreatestElement() {}

/**
* Computes list of dataset,

You have implemented a 'huge' data structure to solve the problem. In this case though, the solution is to use a relatively simple case of memoization. If you work backward from the end of the array, you can use what you have already learned for previous values.....

... in essence, you can use the subsequent NGE's to bootstrap your way to calculate the current cell's NGE.

private static int[] computeNGE(int[] tocompute) {
    if (tocompute == null) {
        throw new NullPointerException();
    }
    if (tocompute.length == 0) {
        return new int[0];
    }
    if (tocompute.length == 1) {
        return new int[]{-1};
    }
    int[] indices = new int[tocompute.length];
    int[] nge = new int[tocompute.length];
    nge[tocompute.length - 1] = -1;
    indices[tocompute.length - 1] = -1;
    for (int i = tocompute.length - 2; i >= 0; i--) {
        int j = i + 1;
        while (j != -1 && tocompute[j] <= tocompute[i]) {
            j = indices[j];
        }
        indices[i] = j;
        nge[i] = j == -1 ? -1 : tocompute[j];
    }
    return nge;
}

The above solution will have close to an \$O(n)\$ time complexity, because, the worst case is a 2-times iteration through the data.

StackExchange Code Review Q#54887, answer score: 4