An algorithm to print the next greater element for each element in the array.
A next greater element for a given element in the array is the first greater element on the right-hand side of the array. If no greater elements are present then print -1.
Example
Input: [4, 5, 2, 25] Output: 4 ---> 5 5 ---> 25 2 ---> 25 25 ----> -1
In the above example the next greater element after 4
is 5
and for 5
is 25
and for 2
is also 25
. As there are no greater element after 25
we return -1
;
Method 1: Using Brute Force approach
Implementation
- We are going to use two nested loops.
- The outer loops picks all the elements one by one and the inner loops looks for the first greater element after the element.
- If no greater elements are found then return
-1
.
let nextGreater = (arr, n = arr.length) => { for(let i = 0; i < n; i++){ let next = -1; //Find the next greater element for(let j = i; j < n; j++){ if(arr[i] < arr[j]){ next = arr[j]; break; } } console.log(next); } }
Input: nextGreater([11, 13, 21, 3]); Output: 13 21 -1 -1
Time complexity: O(n ^ 2);
Space complexity: O(n);
The worst-case occurs when all the elements are sorted in descending order.
Method 2: Using stack for optimization
Implementation
- Add the first element to the stack on initialization.
- Now loop all the other elements with following steps.
- Mark the current element as next.
- If stack is not empty then check its top element with the next.
- If next is greater than the top element, remove element from stack. next is the next greater element for the popped element.
- Keep remove elements from till while elements are smaller than next, This way next becomes the next greater element for all those elements.
- At the end push the
next
in the stack. - After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.
let nextGreaterWithStack = (arr, n = arr.length) => { let stack = new stackUsingLL(); let element, next; //push the first element in the stack stack.push(arr[0]); for(let i = 0; i < n; i++){ next = arr[i]; if(!stack.isEmpty()){ element = stack.pop(); //Print the next greater element while(element < next){ console.log(next); if(stack.isEmpty()){ break; } element = stack.pop(); } //If next element is smaller then add it to the stack if(element > next){ stack.push(element) } } stack.push(next); } //Print the remaining next greaters while(!stack.isEmpty()){ element = stack.pop(); next = -1; console.log(next); } }
Input: nextGreater([11, 13, 21, 3]); Output: 13 21 -1 -1
Time complexity: O(n).
Space complexity: O(n).
Time complexity to find the next greater element in the array using stack.
The worst-case occurs when all the elements are sorted in decreasing order. In this case, every element is processed at most 4 times.
- Initially pushed to the stack.
- Removed from the stack when next element is being processed.
- Pushed back to the stack because next element is smaller.
- Popped from the stack in step 3 of algorithm.