Difficulty: Medium, Asked-in: Amazon, Microsoft
Key takeaway: An excellent problem to learn problem-solving using stack.
Given an array, 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. Elements for which no greater element exist, consider the next greater element as -1.
Examples
Input : A[] = [3, 2, 8, 7, 6, 17, 12], Output: [8, 8, 9, 17, 17, -1, -1]
Explanation: Traversing through the array for each element, we find the next greater element on its right side i.e: NGE of 3 is 8, NGE of 2 is 8, NGE of 8 is 9, NGE of 8 is 17, and so on.
Input : A[] = [4, 5, 2, 25, 10], Output: [5, 25, 25, -1, -1]
Solution Idea and Steps
The basic idea would be to traverse the array and find the next greater element for each element on the right side. We can simply use two nested loops for this.
Solution Pseudocode
int[] nextGreaterElement(int X[], int n)
{
int nextGreater
int output[n]
for (int i = 0; i < n; i = i + 1)
{
nextGreater = -1
for (j = i + 1; j < n; j = j + 1)
{
if (X[i] < X[j])
{
nextGreater = X[j]
break
}
}
output[i] = nextGreater
}
return output
}
Time and space complexity analysis
Here outer loop is runing n times and for each iteration of the outer loop, the inner loop is running n-i-1 times. So total number of loop iteration = n - 1 + n - 2 + .... + 1 + 1 = n(n-1)/2 + 1 = O(n^2). We are performing O(1) operation at each loop iteration loop, so time complexity = O(1) * O(n^2) = O(n^2)
Space complexity = O(1), as we are using a constant amount of memory to find and store the next greater element in the output[] array. Here output[] array will not be the part of the space complexity because it is the part of the output in the given problem. Think!
Solution Idea
Now the critical question is: how do we improve the time complexity. Is there some pattern in the problem which could help us to find an effcient solution? Let's think!
If we look at the input array from left to right, then there are two observations:
Case 1: decreasing order sequence
In this case, the first next greater value is the next greater element of all the values in the decreasing sequence. For example, 6, 4, and 3 are in decreasing order, so the next greater element would be 8 which is the first next greater value. Similarly, 8, 7, and 2, 1 are in decreasing order, so there next greater element would be 12 and 5.
Case 2: increasing order sequence
In this case, all the next value is greater than its previous value, so the adjacent element of each element is the next greater element. For example, 12, 15, and 16 are in increasing order, so the next greater element of 12 would be 15, and the next greater element of 15 would be 16. Similarly, 5, 11, and 13 are in increasing order, so the next greater element of 5 would be 11, and the next greater element of 11 would be 13.
So one idea is: scan from left to right and when we find the first element which is greater than the previous element we stop and save it as the next greater element of the previous element. Even this greater element can be the next greater element of some previous consecutive elements. The critical question is: how do we identify such previous elements? The idea is simple: we need a mechanism to store the occurrences of the previous elements i.e. we can use the stack for this purpose!
Solution Steps
Note: we are pushing indexes into the stack instead of the actual elements.
Solution Pseudocode
int[] getNextGreater(int X[], int n)
{
stack s
int output[n]
s.push(0)
for (int i = 1; i < n; i = i + 1)
{
while (!s.empty() && X[s.top()] <= X[i])
{
output[s.top()] = X[i]
s.pop()
}
s.push(i)
}
while (!s.empty())
{
output[s.top()] = -1
s.pop()
}
return output
}
Time and space complexity analysis
Every element is pushed and popped at most once from the stack. So time complexity = O(n). Space complexity in the worst case = O(n), for the stack.
Solution Idea
Here the idea is similar to the above approach but we process elements from right to left in the array.
Now we run a loop from i = n - 1 to 0 to access each array element to find the next greater element.
Note: Here we are pushing actual elements into the stack.
Solution Pseudocode
int[] getNextGreater(int X[], int n)
{
stack s
int output[n]
s.push(0)
for (int i = n - 1; i >= 0; i = i - 1)
{
while (!s.empty() && s.top() <= X[i])
s.pop()
if(!s.empty())
output[i] = s.top()
else
output[i] = -1
s.push(X[i])
}
return output
}
Time and space complexity analysis
Every element is pushed and popped at most once to the stack. So time complexity = O(n). Space complexity in the worst case = O(n), for the stack.
Enjoy learning, Enjoy thinking, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.