Finding the tallest and find the index number of the next taller guy in a circular queue Input given is:


  Each test case contains two lines. The first line contains a single integer N (1 ≤ N ≤ 105), the number of persons playing the game. The second line contains N integers i(height) (1 ≤ hi ≤ 109) the height of the i-th person. They are numbered 1 to N starting from Druid.


Output given is:


  For each test case print N lines, in the i-th line print 2 numbers, the index of the first person taller than the i-th person on his left, and the index of the first person taller than the i-th person on his right. If no one is taller than the i-th person print -1 -1.


Input is:


3
5
172 170 168 171 169
3
172 169 172 
1
172



The output obtained is:


-1 -1
 1 4
 2 4
 1 1
 4 1
-1 -1
 1 3
-1 -1
-1 -1



The code is:

t = input()

num =  []

def get_druid_index(arr,n):
     druid_max_index = arr.index(max(arr))

     if n == 1:
         num.append(-1)
         num.append(-1)

     for j in range(n):
          if j == druid_max_index:
              num.append(-1)
              num.append(-1)
          else:
              cur = arr[j]
              l = j
              r = j
              for k in range(n):

                   if arr[l] &gt; cur:
                       num.append(l + 1)
                       break


                   if l == 0:
                       l = n


                   l = l - 1 

               for k in range(n):
                   if r == n:
                       r = 0

                   if arr[r] &gt; cur:
                       num.append(r + 1)
                       break

                   r = r + 1


for i in range(t):

   arr = []

   n = input()
   arr = raw_input()
   arr = arr.split()

   get_druid_index(arr,n)
count = 0

for i in range(len(num)/2):
    print num[count],num[count + 1]

    count = count + 2


I optimized the code as much as possible but I get TLE from the online judge. Please offer suggestions for improvements.
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] &lt;= item:
            sdm.pop()
        if sdm:
            left.append(sdm[-1][1] + 1)
        else:
            left.append(-1)
        sdm.append((item, index))
    if max_index &gt; 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] &lt;= 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:

&gt;&gt;&gt; list(taller_to_the_sides([172, 170, 168, 171, 169]))
[(-1, -1), (1, 4), (2, 4), (1, 1), (4, 1)]
&gt;&gt;&gt; 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)]
&gt;&gt;&gt; %timeit taller_to_the_sides(a)
10000 loops, best of 3: 172 µs per loop
a = [random.random() for _ in range(1000)]
&gt;&gt;&gt; %timeit taller_to_the_sides(a)
1000 loops, best of 3: 1.78 ms per loop
a = [random.random() for _ in range(10000)]
&gt;&gt;&gt; %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.