How to reduce the time complexity of the program?

Question

I am solving a problem which states the following: There is a row of buckets numbered from 1 to n. A gardener fills this buckets in a particular fashion. He fills the buckets between two ends l and r including l and r with 1<=l<=r<=n. He does this for k times. We need to find the bucket which is having water equal to the median of volumes in the buckets. I am using a program of time complexity knlgn to solve this. The input is like this: the first line contain n and k seperated by spaces and the next k lines contain pairs l and r for each watering process. I am using an algorithm of nklgn to solve this as follows:

while True:
nk = input().split(' ')
n = int(nk[0])
k = int(nk[1])
a = input().split(' ')
for z in range(len(a)):
    a[z] = int(a[z])
if n==0 and k==0: break

for mn in range(k):
    (x, y) = input().split(' ')
    x = int(x)-1
    y = int(y)-1
    for z in range(x, y+1):
        a[z] += 1
    print(sorted(a)[int(len(a)/2)])

Please help me solve this using a better algorithm and I have encountered a very similar problem at least 3 to 4 times. You may give me some hint in the answer if not entire code.

score 2 · Answer 1 · answered Oct 10 '15 at 19:51

I think you should make use of Segment Tree. This data structure is used to update and retrieve a particular query in O(log(n)) time.

You can update the tree in the following way: first find the nodes which covers the range [l, r] and then store the updated value in those nodes. Process all the queries like this - storing the updated value only in the top node without changing the original nodes. After this, in a pre-order traversal you can update all the necessary nodes in O(n) time. I think this will be a pretty reasonable optimisation.

If you are not aware of this data structure, then I recommend you to first read about it and then try to understand my answer.

score 0 · Answer 2 · answered Oct 10 '15 at 19:35

0

First of all, in the last line, there is no need to do a complete sort of the list when you only need one element.

answered Oct 10 '15 at 19:35

pppery

3,731
22
33
46

please can you give me a code of implementation of median finding in O(n) time. a function implementation would be good – Oct 10 '15 at 19:41
see [this stack overflow question](http://stackoverflow.com/questions/4201292/on-algorithm-to-find-the-median-of-a-collection-of-numbers) – pppery Oct 10 '15 at 20:02

How to reduce the time complexity of the program?

2 Answers2