Given an array arr
of n
integers, print the next greater number for every element. The next greater element of a number k
is the first number to the right of k
which is also larger than k
. If there is no next greater element print -1
The expected time complexity of the solution is O(n)
Example Test Cases
Sample Test Case 1
Input Array: [1, 5, 3, 4]
Expected Output: [ 5, -1, 4, -1 ]
Explanation: The next greater number for element 1
at position 0
is 5, for element 5
which is at position 1
, there is no next greater number, for next element 3
, the next greater number is 4
, for element 4
located at position 3
, there is no next greater number.
Solution
Brute Force
The naive way to solve this problem would be to iterate over each index i
of the array and then compute the next greater number by iterating over the array from position i + 1
onwards. This would involve writing two for loops, with the 2nd for loop nested inside the first loop and the time complexity would be O(n^2)
.
Optimized solution
We can optimize the solution of the problem by using a stack.
At any point of time, an element will be in stack iff we have iterated over that element and we haven’t found the answer for that element yet. As soon as find the next greater number for any element from the stack, we will pop it from the stack.
Let us call the top element of stack as top
Initially we will push element arr[0]
onto the stack.
When we iterate over the remaining elements arr[i]
for (i >= 1), we know either of the two cases will occur:
arr[i] > top
: In this case , the answer fortop
will bearr[i]
. Therefore, we will keep on popping out thetop
elements from stack untiltop
becomes thanarr[i]
and mark the answer for all the popped elements asarr[i]
and then insertarr[i]
onto the top of the stack.-
top >= arr[i]
: In this case, we will just push thearr[i]
onto the top of the stack