How do I find the largest element on the left of an element that is smaller than the element?
Suppose I have an array of integers:
{ 3, 1, 6, 8, 2, 0, 1 }
I need to find the maximum item on the left of each item that is smaller than the item, or print -1
if that maximum item does not exist. So the solution to this problem would be:
{ -1, -1, 3, 6, 1, -1, 0 }
I can solve this in O(n^2)
two loops. The inner loop will find the maximum element that is less than the given element. But is there a better way to solve this problem?
source to share
While this question is not about finding the rightmost element on the left side which is smaller , the problem for which there is a nice linear time algorithm that includes a stack is closely related. To solve this problem, sort the array index and value pairs by value, then run the algorithm from the linked question, treating the indexes as values. This avoids the persistent factors imposed by the binary search tree.
Since sorting of individual elements is linear-temporal, reducible to this task, the running time of O (sort (n)) is more or less optimal.
Python implementation (thinner than expected, please note that sorted
shouldn't change items comparing the same).
def alg(lst):
indexes = sorted(range(len(lst) - 1, -1, -1), key=lst.__getitem__)
stack = []
out = [-1] * len(lst)
for i in indexes:
while stack and i < stack[-1]:
del stack[-1]
if stack:
out[i] = lst[stack[-1]]
stack.append(i)
return out
print(alg([3, 1, 6, 8, 2, 0, 1]))
source to share
You can save the numbers you found on the tree map. Save their index along with the number. When you go to the index number i
, look in the tree for the highest number below array[i]
. Using lowerEntry
, you can do this in Log 2 N time, making the total time N * Log 2sub> N
source to share