Next largest element for each element - PrismoSkills
Problem: Given an unsorted array, print the nearest larger element for each element.
An O(n) solution can be implemented if we consider the following property of the problem:
This can be called as a Decreasing Stack
Read full article from Next largest element for each element - PrismoSkills
Problem: Given an unsorted array, print the nearest larger element for each element.
An O(n) solution can be implemented if we consider the following property of the problem:
By definition of the problem, we only need to consider elements towards the right of an element for finding the next larger element.
If instead of finding next larger element towards the right side of every element, we print (and discard) those elements whose next larger element is the current element, then we can find a better solution.
This approach is more efficient, because at every step, some of the elements are getting discarded.
We use a stack to store elements towards the left side of current elements which could not be discarded (because their next larger element has not come yet).If instead of finding next larger element towards the right side of every element, we print (and discard) those elements whose next larger element is the current element, then we can find a better solution.
This approach is more efficient, because at every step, some of the elements are getting discarded.
This can be called as a Decreasing Stack
Read full article from Next largest element for each element - PrismoSkills
