I think you can write a linear time solution borrowing ideas from this. The idea is to keep a stack of decreasing maxima (SDM). Let's consider first the problem without taking into account the circularity...
Say your input was [7, 4, 5, 3]. When you are processing the third item (5), you want your SDM to be [(7, 1), (4, 2)], where he second item in the tuple is the 1-based index of that item in the original array, as per your problem's description. You search the SDM for the last entry larger than the item being processed, which in this case is (7, 1), so the index of the first item larger than 5 to its left is 1. You then discard all items in the SDM to the right of this one, and insert the current value in it's position, so the SDM now becomes [(7, 1), (5, 2)]. Rinse, repeat, and you have all your first items larger than to the left. For the symmetric item to the right, do the same scanning from right to left.
At first this may seem as an \$O(n^2)\$ algorithm, since you have to search a list that could potentially be as large as the array (e.g. if the input is monotonically decreasing) for every item. Because the SDM is sorted, you could try to use binary search to make that bound \$O(n\log n)\$, but that would actually slow down the process!
You have to keep in mind that, as the stack is being searched sequentially, entries that aren't larger than the one being processed are being removed from the stack! So the more work an item requires to find it's answer, the easier it makes it for the ones remaining. A careful analysis of this shows that, on average, each item takes constant time to process, so the resulting time complexity is \$O(n)\$, which is basically as good as it gets.
You can factor in the circularity of the problem into the above approach, by first finding the maximum, and always starting your circular iteration, whether to the left or right, from it, so that you will always have the maximum in your SDM.
But enough talking, here's an implementation:
def taller_to_the_sides(list_):
max_index = list_.index(max(list_))
sdm = []
left = []
for index in range(len(list_)):
index += max_index
index %= len(list_)
item = list_[index]
while sdm and sdm[-1][0] <= item:
sdm.pop()
if sdm:
left.append(sdm[-1][1] + 1)
else:
left.append(-1)
sdm.append((item, index))
if max_index > 0:
left = left[-max_index:]+left[:-max_index]
sdm = []
right = []
for index in range(len(list_)):
index = max_index - index
index %= len(list_)
item = list_[index]
while sdm and sdm[-1][0] <= item:
sdm.pop()
if sdm:
right.append(sdm[-1][1] + 1)
else:
right.append(-1)
sdm.append((item, index))
right = right[max_index::-1] + right[:max_index:-1]
return zip(left, right)
There are two almost identical blocks in that function that should probably be refactored into a common external function, but I felt it would better show what was going on to keep them separated.
Anyway, when you run this you get the expected output:
>>> list(taller_to_the_sides([172, 170, 168, 171, 169]))
[(-1, -1), (1, 4), (2, 4), (1, 1), (4, 1)]
>>> list(taller_to_the_sides([169, 172, 170, 168, 171]))
[(5, 2), (-1, -1), (2, 5), (3, 5), (2, 2)]
The second example is the first one shifted one item to the right, to show that maxima not in the first position also work. And since the algorithm is linear, it handles large inputs reasonably fast:
a = [random.random() for _ in range(100)]
>>> %timeit taller_to_the_sides(a)
10000 loops, best of 3: 172 µs per loop
a = [random.random() for _ in range(1000)]
>>> %timeit taller_to_the_sides(a)
1000 loops, best of 3: 1.78 ms per loop
a = [random.random() for _ in range(10000)]
>>> %timeit taller_to_the_sides(a)
100 loops, best of 3: 18.3 ms per loop
To be honest, I was expecting it to be faster, but do notice also how the time scaling is roughly linear, as expected.
