Next greater element in array

Tags: , , ,

Next greater element in array

Given an array of integers, find next greater element for current element in array i.e. for each a[i], find minimum j so that a[j] > a[i] and j>i.

For the rightmost element, value will be -1. For any i, if there is no such j, then result for that too will be -1.
In simple terms, we need to find nearest greater number for each element in given array. For example:

Next greater element in array: Line of thought

Brute force method would be to scan array in two loops. For each element in array, scan remaining right side elements and find out the greater number. Complexity of code is O(n2). How can we do better and solve this in linear time?

What if while scanning the array, we keep track of all numbers for which greater number is yet not found. Idea is that whenever we see a number, check if there are elements which are already visited in array and yet there is no greater number assigned to them. If there are such elements, we check if current element is greater than them. If yes, then for all those numbers which are less than current element, next greater element will be current number. However, we have yet not find next greater number for current number, so put it back to list.

This list will be in decreasing order, as we will be removing all the numbers which are less than current number fro the list. They got current number as next greater number. All remaining numbers on list will be greater than current number. What will be the best data structure store this list? Stack, as we are interested in last element first.
This problem is very similar to stock span problem.

Next greater element in array : Algorithm

  1. Push first element on to stack
  2. While(!stack.empty && stack.peek() < current) stack.pop()
  3. Pair all popped numbers with current number
  4. If stack.top() > current or stack.empty(), stack.push(current)
  5. After scanning all elements in array, print all elements in stack paired with -1 as there is no greater element on right side of these elements.

Next greater element in array : Implementation

package com.company;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 19.9.18.
 */
public class NextGreaterElement {
    public static ArrayList<Pair<Integer, Integer>> nextGreaterElement(int[] a){

        Stack<Integer> s = new Stack();
        ArrayList<Pair<Integer,Integer>> nextGreater = new ArrayList<>();

        for(int i=0; i<a.length; i++){
            while(!s.empty() && a[i] > s.peek()) {
                nextGreater.add(new Pair<>(s.pop(), a[i]));
            }
            s.push(a[i]);
        }
        while(!s.empty()) nextGreater.add(new Pair<>(s.pop(), -1));
        return nextGreater;
    }

    public static void main(String args[]){
        int a[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98};
        ArrayList<Pair<Integer, Integer>> nextGreater = nextGreaterElement(a);

        System.out.println(nextGreater);

    }
}

Let’s workout an example: A = {5,6,3,35,23,6,8}. we start with empty stack = []. For the first element, we have empty stack, add 5 to stack. Now, stack = [5]

For next element 6, stack is not empty and element at the top of stack is less than 6. We will pop 5 from stack and create a pair. Output = {(5,6)}, we will push 6 back on to stack. stack = [6]

Next element is 3, which is less than top of stack, do nothing, and put the element on top of stack, stack = [6,3]

For 35, pop out 3 and 6 from stack and create pairs and add them to list. Output = {(5,6),(6,35), (3,35)}, add 35 to stack, stack = [35]

Next element is 23, which is less than top of stack, do nothing, and put the element on top of stack, stack = [35,23]

Again element 6, is less than top of stack, do nothing, and put the element on top of stack, stack = [35,23,6]

For 8, top of stack is less than 8, so pop and create pair and add to output. Output = {(5,6),(6,35), (3,35),(6,8)}, add 8 to stack, stack = [35,23,8]

Now there are not elements left, pop everything from stack and pair them with -1. Final output should be {(5,6), (6,35), (3,35), (6,8), (8, -1), (23, -1), (35, -1)}

Complexity of algorithm to find next greater element in array will be O(N) with extra space complexity of O(N) for stack.

Please share if there is something missing or wrong. If you are interested in taking personalized coaching for your interview preparations, please reach out to communications@algorithmsandme.com