7
\$\begingroup\$

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:

  1. For any array, rightmost element always has next greater element as -1.
  2. For an array which is sorted in decreasing order, all elements have next greater element as -1.
  3. 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
    
  4. 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, where dataset is a tuple of
     * (currentInt, nextGreatestelement)
     * 
     * @param a     the array
     * @return      list of dataset
     */
    public static List<DataSet> getNextGreatestElement(int[] a) {

        final List<DataSet> dataSetList = new ArrayList<DataSet>();
        final Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < a.length; i++) {

            while (!stack.isEmpty() && stack.peek() < a[i]) {
                dataSetList.add(new DataSet(stack.pop(), a[i]));
            }

            stack.push(a[i]);
        }

        while (!stack.isEmpty()) {
            dataSetList.add(new DataSet(stack.pop(), -1));
        }


        return dataSetList;
    }
}

public class NextGreatestElementTest {

    @Test
    public void test1() {
        int[] a1 = {2, 3, 4, 5};
        List<DataSet> ds1 = new ArrayList<DataSet>();
        ds1.add(new DataSet(2, 3));
        ds1.add(new DataSet(3, 4));
        ds1.add(new DataSet(4, 5));
        ds1.add(new DataSet(5, -1));
        assertEquals(ds1,  NextGreatestElement.getNextGreatestElement(a1));
    }


    @Test
    public void test2() {
        int[] a2 = {3, 2, 1};
        List<DataSet> ds2 = new ArrayList<DataSet>();
        ds2.add(new DataSet(1, -1));
        ds2.add(new DataSet(2, -1));
        ds2.add(new DataSet(3, -1));
        assertEquals(ds2, NextGreatestElement.getNextGreatestElement(a2));
    }

}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.