PROBLEM LINK:
Author: Full name
DIFFICULTY:
Easy-Medium
PROBLEM:
Find the number of consecutive numbers before a[i] such that they are less than or equal to a[i]
EXPLANATION:
This problem is related to the stock span problem.
The simple method is to traverse the input array. For every element being visited, traverse elements on left of it and increment the span value of it while elements on the left side are smaller.
However, a more-efficent linear time algorithm is possible since we only want the difference between current height and place where height was higher. Thus we can maintain a stack of heights in decreasing order. If height less than a[i] is obtained, we pop it. Else, the diffrence of positons is taken from the person at top of the stack and the current person is pushedd to the top of the stack.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.