Aim- Given an array of integers we need to find the next greater element of each one which means a number greater than that value and appearing on the nearest right or “-1” if no such element exists.
Ex- 1 2 9 3 7 6
Ans- 2 9 -1 7 -1 -1
Naive’s Approach-
Use two ‘for’ loops first will iterate over the value, of which nearest neighbor is to be found and others will iterate over its right to look for the nearest larger value. In the worst case, it is pretty clear that this algorithm will take O(n^2) time.
Let’s look at its implementation-
Time Complexity- O(n^2)
Auxiliary Space Complexity-O(1).
The worst case is when all the time comparison is for the maximum time that means j is n for each index i, that is a reverse sorted array.
Can We Do better Like O(n) in time by using some extra space??
Prerequisite - Basic knowledge of Stack Data Structure.
Idea - Basically we will start with last index and will store values in the stack in a particular fashion described below by which our task will be completed in one traversal -> O(n).
Algorithm-
First, add the last element to the stack. Now run a loop for N-1 to 0:->
a) For each element remove all the elements smaller than or equal to comparison with the current number present on top of the stack.
b) Now if stack becomes empty print -1 which means no greater element was present on right else print the topmost element.
c) Now push the current element to stack.
d) Repeat the above step till i becomes 0.
In this way, our task got completed in just one traversal in exchange for memory of O(n). Implementation-
1. Time Complexity-O(n)
2. Space Complexity-O(n)
Note - Similarly you can manipulate this trick to find previous greater element, previous smaller element and next smaller element.
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/next-greater-element-ii/
https://www.interviewbit.com/problems/nearest-smaller-element/
This article is contributed by Adarsh Agrawal
So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army 😊