Next Greater Element Editorial

Practice Problem Link: Next Greater Element

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array of positive integers A, find the first greater number for every element on its right. If a greater number does not exist, use -1.

Naive Approach

We can use two nested loops, to search for the next greater element of the ith element in the array. If we find the next greater element, we push it into the list, else we push -1 into the list and finally return it.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

vector<int> getNextGreaterElement (vector<int> &A) {
	int n = A.size();
	vector<int> nextGreater;
	for(int i = 0; i < n; i++) {
		bool possible = false;
		for(int j = i + 1; j < n; j++) {
			if(A[j] > A[i]) {
				nextGreater.push_back(A[j]);
				possible = true;
				break;
			}
		}
		if(!possible) {
			nextGreater.push_back(-1);
		}
	}
	return nextGreater;
}

Java

class Solution {
	int[] getNextGreaterElement (int[] A) {
		int n = A.length;
		int nextGreater[] = new int[n];
		for(int i = 0; i < n; i++) {
			nextGreater[i] = -1;
		}
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				if(A[j] > A[i]) {
					nextGreater[i] = A[j];
					break;
				}
			}
		}
		return nextGreater;
	}
}

Optimal Approach

We can use stack to optimize the above approach. The steps for the algorithm are,

1. Push the first element to the stack.
2. For the remaining element, mark the current element as next.
3. If the stack is not empty, compare the top element of the stack with next.
4. If next > top, pop from the stack, nextis the next greater element of the popped element.
5. We keep popping from the stack, till nextis greater the top of the stack, next is the next greater element for all these popped elements.
6. Finally, we push next into the stack.
7. At the end, pop all the remaining elements from the stack and store their next greater element as -1.

Finally we can return the calculated list.

Analysis:

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation:

C++

vector<int> getNextGreaterElement (vector<int> &A) {
	int n = A.size();
	stack<int> s; 
	vector<int> nextGreater(n);
    for (int i = n - 1; i >= 0; i--){
        while(!s.empty() && A[s.top()] <= A[i]) {
			s.pop();
		}
        if(s.empty()) {
			nextGreater[i] = -1;
		}
        else {
			nextGreater[i] = A[s.top()];
		}
        s.push(i);
    }
    return nextGreater;
}

Java

class Solution {
	int[] getNextGreaterElement (int[] A) {
		Stack<Integer> stack = new Stack<>();
		ArrayList<Integer> nextGreater = new ArrayList<>();
        for (int i = A.length - 1; i >= 0; i--) {
            while (!stack.empty() && A[i] >= stack.peek()) {
                stack.pop();
			}
            nextGreater.add(stack.empty() ? -1 : stack.peek());
            stack.push(A[i]);
        }
		int result[] = new int[A.length];
		int k = 0;
         for (int i = A.length - 1; i >= 0; i--) {
            result[i] = nextGreater.get(k++);
		 }
		return result;
	}
}