# Find a weighted median for unsorted array in linear time

For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time.

It is very simple to do that in exponential time.

So let's say that we have an array, each item of this array has 2 attributes - price and weight. The goal is to find an item x such that: SUM of weights of all items which costs less than x <= SUM(all items)/2 and SUM of weights of all items which costs more than x <= SUM(all items)/2.

If the array was sorted, it would be simple:

Go from the first item one by one, count sum and if the sum becomes greater that SUM(all items)/2, then you found desired item.

Could you give me some hint how to find such item in linear time?

• Why not first sort the array then do what you proposed in question. Or you are looking for algorithm to run precisely in O(n) time. – Prateek Apr 21 '16 at 13:56
• @Prateek "in linear time" in the question title does seem to imply that. – Tom van der Zanden Apr 21 '16 at 14:00

Let $A$ be an input array containing $n$ elements, $a_i$ the $i$-th element and $w_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array length is $\leq 2$, find the weighted median by exhaustive search. Otherwise, find the (lower) median element $a_x$ using the worst case $O(n)$ selection algorithm and then partition the array around it (using the worst case $O(n)$ partition algorithm from QuickSort). Now determine the weight of each partition. If weight of the left partition is $< \frac{1}{2}$ and weight of the right partition is $\leq \frac{1}{2}$ then the weighted (lower) median is $a_x$. If not, then the weighted (lower) median must necessarily lie in the partition with the larger weight. So, you add the weight of the "lighter" partition to the weight of $a_x$ and recursively continue searching into the "heavier" partition. Here is the algorithm's pseudocode (written in Latex).

FIND-WEIGHTED_LOWER_MEDIAN(A)
if $n$ == 1
return $a_1$
elseif $n$ == 2
if $w_1 \geq w_2$
return $a_1$
else
return $a_2$
else
determine $a_x$, the (lower) median of A
partition A around $a_x$
$W_{low}$ = $\sum\limits_{{a_i} < {a_x}} {{w_i}}$
$W_{high}$ = $\sum\limits_{{a_i} > {a_x}} {{w_i}}$
if $W_{low} < \frac{1}{2}$ AND $W_{high} \leq \frac{1}{2}$
return $a_x$
else if $W_{low} \geq \frac{1}{2}$
$w_x = w_x + W_{high}$
B = \{ a_i \in A: a_i \leq a_x \}
FIND-WEIGHTED_LOWER_MEDIAN(B)
else
$w_x = w_x + W_{low}$
B = \{ a_i \in A: a_i \geq a_x \}
FIND-WEIGHTED_LOWER_MEDIAN(B)


Now let's analyze the algorithm and derive its complexity in the worst-case. The recurrence of this recursive algorithm is $T(n) = T(\frac{n}{2} + 1) + \Theta(n)$. Indeed, we have no more than a recursive call on half the elements plus the (lower) median. The initial exhaustive search on up to 2 elements costs $O(1)$, determining the (lower) median using the select algorithm requires $O(n)$, and partitioning around the (lower) median requires $O(n)$ as well. Computing $W_{low}$ or $W_{high}$ is again $O(n)$. Solving the recurrence, we get the complexity of the algorithm in the worst case, which is $O(n)$.

Of course, a real implementation should not use the worst case $O(n)$ selection algorithm, since it is well known that the algorithm is not practical (it is of theoretical interest only). However, the randomized $O(n)$ selection algorithm works pretty well in practice and can be used since it's really fast.

• Can this algorithm be modified to find both the medians? – Abhijit Sarkar Nov 22 '18 at 1:44

You can do binary search for the price of x that satisfies the criterion. Computing the sum would take linear time each iteration (giving $O(n\log n)$ time) but you can compute the sum faster if you reuse work from previous iterations.

• @Torn Thank you for an advice. I understand the part with reusing work from previous iterations and in fact, I was thinking about binary search too. But I can't figure out what to search for because it's unsorted so If I choose some item, how to choose another in next iteration of binary search? For example if I have array - prices = [6,4,3,5,0,1,2] with weights = [10,20,30,15,5,10,20] – Milano Apr 21 '16 at 19:34
• You don't need the array to be sorted to do binary search, you just need to be able to find the element with the median price (out of the items remaining). – Tom van der Zanden Apr 21 '16 at 19:36
• Ok so: 1. Sum is 110, middle is 55. 2. Start with item on index 0, which is a price 6 with weight 10. And now I'm stucked, how to use binary search, what to search for? Thanks – Milano Apr 21 '16 at 20:11
• Another approach I was thinking about is to start with 1st item which is trivialy the result, then compute result adding next item etc. But it seems to be higher than linear. – Milano Apr 21 '16 at 20:16

This answer is very similar to Massimo's except with a (hopefully) simpler style/structure of phrasing it and in addition includes the solution to find the second weighted median as well.

If you want just a hint, just look at step 1), and read no further. If you want more hints, continue to next step.

## Assumptions:

Input is in two different arrays: Prices[], and Weights[] Whenever values in Prices[] are rearranged, values in Weights[] are also rearranged to keep the correspondence between indexes.

## Approach:

1. Using the method from either Randomized selection, or Deterministic selection
algorithm, partition the Prices around a selected Pivot element.
2. Calculate the sum of all weights in the Left Partition as L, and the sum of
all weights in the Right Partition as R.
3. Let P be a 'reference' to the weight of the Pivot element.
4. Calculate the total weight of all the elements, L + P + R as S
5. a) If L > S/2:
P += R (Add weight of all elements in right partition to the Pivot)
Change array upper bound to end at Pivot element.
go to step 1.
b) Else If R > S/2:
P += L (Add weight of all element in left partition to the Pivot)
Change array lower bound to begin at the Pivot element.
go to step 1.
c) Else:
Pivot is the Median.
i) If L + P == S/2:
Successor of the Pivot element is also a Median.
Linear scan the Right partition to find the element with Min Price
as the Successor.
ii) Else If P + R == S/2:
Predecessor of the Pivot element is also a Median.
Linear scan the Left partition to find the element with Max Price
as the Predecessor.
return the Medians
(Done)


## Correctness:

Step 5.a)

If L > S/2, the median cannot be in the Right Partition. Because, if it be so, L will only get larger and violate the requirement that L must be less than or equal to S/2. Hence, we look for median in the Left Partition

Step 5.b)

If R > S/2, the median cannot be in the Left Partition. Because, if it be so, R will only get larger and violate the requirement that R must be less than or equal to S/2. Hence, we look for median in the Right Partition

Step 5.c.i)

L + P <= S/2 implies R = S/2 and L + P = S/2, because L + P + R = S.

Step 5.c.ii)

P + R <= S/2 implies L = S/2 and P + R = S/2, because L + P + R = S.

## Complexity:

The number of elements scanned to calculate L, and R is no more than the number of elements scanned to partition the array in each iteration/reduction.

Hence, the complexity of the solution is same as that of the Selection algorithm used, which is average O(n) if Randomized selection, or worst case O(n) if Deterministic selection is chosen.

In addition, 5.c.i) or 5.c.ii) do a one time scan of a maximum of n-1 elements in case there is a possibility for a second median, which doesn't add significantly to already deduced overall complexity of either average or worst case O(n)

## Notes:

The approach is easy to implement in a non recursive way, and i also have some notes not though totally relevant to the question, but could be relevant to many people who end up here: https://thoughtvalve.blogspot.com/2020/03/why-only-2-weighted-medians-at-most.html