Given an array of integers of length N, the task is to find the next greater element for every element.
The next greater element for an element is the first greater element on the right side of the array.
If no greater element exists, consider the next greater element as -1.
Input: arr[] = [3, 2, 8, 7, 6, 17, 12], Output: [8, 8, 17, 17, 17, -1, -1]
Input: arr[] = [4, 5, 2, 25, 10], Output: [5, 25, 25, -1, -1]
Solutions
Method 1: Using Stack
We can solve this problem using Stack easily.
The idea is to maintain elements in a stack in descending order so that for every element in the array, the next greatest element can be obtained from the stack.
Traverse the array from the right and keep removing elements from the stack until the top element in the stack is less than the current element in the array.
If the stack is still not empty, the top () element will be the next greater for the current element in the array; otherwise, assign -1.
Complexity
The time complexity of this solution is O(N) and space complexity is O(N).