Find next greater indexes

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[]{13, 8, 1, 5, 2, 5, 9, 7, 6, 12};
        System.out.println(Arrays.toString(findNextGreaterIndexes(nums)));
    }
    
    private static int[] findNextGreaterIndexes(int[] nums) {
        // Next greater indexes mean the values should be strictly increasing, 
        // so we use ">"
        
        // Time Complexity: O(n), Iterating through all elements in array
        // Space Complexity: O(n), In worst case, we need to store all elements in stack
        
        // Edge case
        if(nums==null) {
            return null;
        }
        
        // Initialise an empty stack
        Stack<Integer> stack = new Stack<>();
        
        // Create a result int[] where we will store next greatest indexes
        int[] result = new int[nums.length];
        Arrays.fill(result, -1); // Initialise all the values in result with -1
        
        for(int i=0;i<nums.length;i++) { // Iterate through input array
            // nums[stack.peek()] --> Numerical value of index on top of stack
            // nums[i] --> current number
            // Loop through stack and check 
            // Since need to find strictly increasing index, we check 
            // if the numeric value of index stored in top of stack < than current number 
            // This would help us find strictly increasing index
            while(!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                // As we found suitable value for the index on stack.peek(),
                // We pop it, which means we found greater index value for it
                int stackTopIdx = stack.pop();
                // Store the current index at stacktopidx positiaaon in result
                result[stackTopIdx] = i; 
            }
            // Push the current index to stack
            // By following above while loop, the monotonic property of stack is always maintained
            stack.push(i);
        }
        return result;
    }
}

Understanding of `while` loop comparison

Final Result

Last updated

Was this helpful?