4
\$\begingroup\$

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] > 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] > 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.

\$\endgroup\$
  • \$\begingroup\$ Is TLE a kind of time-limit excedeed? \$\endgroup\$ – Caridorc Jul 19 '15 at 13:36
  • 1
    \$\begingroup\$ Yes Caridorc TLE (Time-limit exceeded) \$\endgroup\$ – susil95 Jul 19 '15 at 13:40
  • \$\begingroup\$ You are on topic then. Welcome! \$\endgroup\$ – Caridorc Jul 19 '15 at 13:42
  • \$\begingroup\$ I think the starting 3 in the input is an error and should be deleted. \$\endgroup\$ – Caridorc Jul 19 '15 at 13:46
  • 1
    \$\begingroup\$ No, the starting 3 is input for "t" and is used to get the number of test cases. \$\endgroup\$ – susil95 Jul 19 '15 at 15:00
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$
  • First, a couple of notes on readability:

    Your get_height function actually returns highest person index (druid?). So, it should be named accordingly: get_druid_index.

    Same goes to gpri - absolutely impossible to figure out what that means without going through code. I'd suggest to rename it to druid_index.

  • Now, the algorithm:

    Let's define 3 variables:

    • druid_index=get_druid_index()
    • taller_left=-1
    • taller_right=-1

    and another one, person_index, that we get from the input.

    Assuming druid is on the left (druid_index<person_index) go over indexes person_index down to druid_index to find taller_left. Go over indexes person_index to druid_index to find taller_right.

    Of course, you need to account for array limits. The logic is opposite if druid is on the right.

    The complexity of proposed solution is \$O(2n)\$. You have to pass the array once to get the druid_index and once more to get the taller indices.

\$\endgroup\$
  • \$\begingroup\$ Unless I'm understanding you wrong, your solution is actually \$O(n^2)\$, as you potentially have to scan the full array (e.g. if druid is at the first position) for every item in the array. \$\endgroup\$ – Jaime Jul 19 '15 at 16:06
  • \$\begingroup\$ @Jaime why would you need to find the druid for every item in the array? It's position doesn't change \$\endgroup\$ – Daniel Sokolov Jul 19 '15 at 16:33
  • \$\begingroup\$ The druid stays put, but for every item in the array you have to scan the array from it's position to druid's, both to the right and left, don't you? \$\endgroup\$ – Jaime Jul 19 '15 at 17:04
  • \$\begingroup\$ @Jaime you only need to scan the array once. let's say druid index is di and person index is pi. And, let's assume di < pi. You need to scan the array between di+1 and pi-1 to find the first taller person on the left of pi and another scan between pi+1 and di-1 to find the person on the right. one full scan of the array in worst case. \$\endgroup\$ – Daniel Sokolov Jul 19 '15 at 17:24
  • \$\begingroup\$ But you have to do that for every person, don't you? \$\endgroup\$ – Jaime Jul 19 '15 at 18:22
3
\$\begingroup\$

I though of another algorithm...

This solution has a bit less straightforward logic, but it finds the answer in \$O(n)\$.

I figured you could use any depending on your needs, so I'm posting it as a separate answer.

  • go over the array starting from person_index.

  • first taller person becomes druid_index.

  • continue through the rest of the array...

  • if you find person taller than person_index, but shorter than druid_index - it becomes taller_right. taller_right can be set multiple times, when last assignment will be the 'real' taller_right (closest right neighbor taller to person_index)

  • if you find person taller than druid_index (say at index j), set taller_left = druid_index, druid_index = j. Note, that you set taller_left only once (as you need the closest neighbor) , but druid_index can be set multiple times.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.