Find the Next Greater Element Using Stack

The Next greater Element for an integer is the first greater element from the right side of it in the array. In case there is no element greater than the current integer in the right sub-array then the next greater element will be -1.

For example

package org.wesome.dsalgo;

import java.util.Stack;
import java.util.stream.IntStream;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        Stack<Integer> stack = new Stack<>();
        int nextGreaterElementArray[] = new int[arr.length];
        /* if stack is not empty, then
        pop an element from stack. if the popped element is smaller than next, then
        a)print the pair
        b)keep popping while elements are smaller and stack is not empty */
        for (int i = arr.length - 1; i >= 0; i--) {
            /*if stack is not empty and top is smaller than array item from last, then keep removing them            we will find monotonic sequence, i.e.the decreasing order, if yes then keep popping element*/
            if (!stack.empty()) {
                while (!stack.empty() && arr[i] >= stack.peek()) {
                    stack.pop();
                }
            }
            /*if stack is empty , means there was no element greater than current array element, so put -1*/
            if (stack.empty()) {
                nextGreaterElementArray[i] = -1;
            } else {
                /*if stack is not emtpy, means it is graeter then the current array element, put it as nextGreaterElementArray*/
                nextGreaterElementArray[i] = stack.peek();
            }
            stack.push(arr[i]);
        }
        IntStream.range(0, arr.length).mapToObj(i -> arr[i] + " --> " + nextGreaterElementArray[i]).forEach(System.out::println);
        return nextGreaterElementArray;
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class NextGreaterElementTest {
    @Test
    void nextGreaterElementTest1() {
        int[] arr = new int[]{11, 13, 21, 3};
        int[] result = new int[]{13, 21, -1, -1};
        Assertions.assertArrayEquals(result, NextGreaterElement.nextGreaterElement(arr));
    }

    @Test
    void nextGreaterElementTest2() {
        int[] arr = new int[]{1, 2, 3, 4, 5};
        int[] result = new int[]{2, 3, 4, 5, -1};
        Assertions.assertArrayEquals(result, NextGreaterElement.nextGreaterElement(arr));
    }

    @Test
    void nextGreaterElementTest3() {
        int[] arr = new int[]{5, 4, 3, 2, 1};
        int[] result = new int[]{-1, -1, -1, -1, -1};
        Assertions.assertArrayEquals(result, NextGreaterElement.nextGreaterElement(arr));
    }

    @Test
    void nextGreaterElementTest4() {
        int[] arr = new int[]{-1, -2, -3, -4, -5};
        int[] result = new int[]{-1, -1, -1, -1, -1};
        Assertions.assertArrayEquals(result, NextGreaterElement.nextGreaterElement(arr));
    }
}

plugins {
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}