Find a weighted median for unsorted array in linear time

Question

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 $x$ of this array has two attributes - price $c(x)$ and weight $w(x)$. The goal is to find an item $x$ such that $$ \sum_{y\colon c(y) < c(x)} w(y) \leq \frac{1}{2} \sum_y w(y) \text{ and } \sum_{y\colon c(y) > c(x)} w(y) \leq \frac{1}{2} \sum_y w(y). $$

If the array was sorted by price, it would be simple:

Go from the first item one by one, count sum and if the sum becomes greater that half the total weight, then you found the desired item.

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

Answer 1

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.

Answer 2

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.

Answer 3

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