Increasing programming efficiency to O(n) from O(n^2)

Question

Let's say you have an array of numbers and a queries array:

array = [1,3,5,6,9]
queries = [5,9,3]

We need to find the number of operations required i.e. add 1 or subtract 1 from the array to bring all numbers of the array to match the element from the queries array.

For example:

• For query 5, number of operations required to bring all elements of array to 5 is abs(1-5) + abs(3-5) + abs(5-5) + abs(6-5) + abs(9-5) = 4+2+0+1+4 = 11.

• For query 9, it would be 21.

• For query 3 it would be 13.

Is there a way to do this with time complexity better than O(len(array) x len(queries)) ?

My function to do this in python is as follows

def find_min_costs(array,queries):
    for query in queries:
        cost = 0
        for arr in array:
            cost+= abs(arr-query)
        print(cost,end = ' ')

but the time complexity of my code is O(len(array) x len(queries))

I would like to do this with a better time complexity such as O(len(array))

Answer 1

Sort the input array (if it is not sorted already).

Now, for every query q, find the position pos where the query number would be placed in the array (use binary search).

Next, observe that, for all numbers to the left, array[1], ..., array[pos], their impact would be q - array[i]. The total is pos * q - sum_of_array_from_1_to_pos.

Similarly, for all numbers to the right, array[pos+1], ..., array[n], their impact would be array[i] - q. The total is sum_of_array_from_pos+1_to_n - (n-pos) * q.

If you compute prefix sums of the sorted array in advance, the above quantities can be found in O(1).

In total, the preparation step is sorting the array in O(n log n), where n is the length of the array. Then computing prefix sums in O(n).

For each query, the work can be done in O(log n) for binary search and then O(1) for computing the answer. The total is O(m log n), where m is the number of queries and n is the length of the array.

---

How to use prefix sums: if we have prefix sums p[i] = array[1] + array[2] + ... + array[i], then a quantity like sum_of_array_from_x_to_y is just p[y] - p[x-1].

How to compute prefix sums: p[0] = 0, p[i] = p[i - 1] + array[i].