# A complicated variant of Weighted Median problem

Suppose, we have an array of numbers $x_j$ and their corresponding weights $w_j$ where $\sum_j w_j \gt 1$. Now we need to find $x_m$ such that

$$\sum_{j=1}^{m-1} w_j \lt 1/2 \quad \text{and} \quad \sum_{j=m+1}^{n} w_j \ge 1/2$$

Moreover, $x_m > x_j$, $x_m < x_k$ where $j \ne k$. i.e. a solution should be like this --

$$\underbrace{x_1, x_2, \ldots, x_{m-1}}_{\lt \, x_m}, x_m, \underbrace{x_{m+1}, \ldots, x_{n-1}, x_n}_{\ge \, x_m} \\ \underbrace{w_1, w_2, \ldots, w_{m-1}}_{\lt \, 1/2}, w_m, \underbrace{w_{m+1}, \ldots, w_{n-1}, w_n}_{\ge \, 1/2}$$

Moreover, it was also mentioned that I may use Dynamic Programming that could be bounded by $O(n\lg n)$.

EDIT:

$\{x_j, w_j\}: \quad x_j \text{ is the value and } w_j \text{ is the weight.}$

Example Input: $\{10, 0.4\}, \, \{5, 0.1\}, \, \{6, 0.9\}, \, \{2, 0.3\}, \, \{3, 0.1\}$

Example Output: $\{2, 0.3\}, \, \{3, 0.1\}, \, \underbrace{\{5, 0.1\}}_{x_m}, \, \{6, 0.9\}, \, \{10, 0.4\}$

How I tried

Step 1: First sort the list according to $w_j$. -- $O(n \lg n)$

Step 2: Start from the first element from the left, add the weights $w_j$ until $\sum_j w_j \ge \, 1/2$. The current $x_j$ is the $x_m$. -- $O(n)$

Step 3: Stop, now we have two lists. One is on the left $L=\{x_1, x_2, \ldots, x_{m-1}\}$ and the other is on the right $R = \{x_m, x_{m+1}, \ldots, x_n\}$.

Step 4: Go through the list $L$, if there is any value $x_k > x_m$, move $x_k$ into $R$ at an appropriate position. Do this until all elements in $L$ is smaller than $x_m$. -- $O(n^2)$

Step 5: if $L \ne \emptyset$, $x_m$ is the answer, otherwise $x_1$ is the answer.

The overall complexity will be $O(n \lg n) + O(n) + O(n^2) \approx O(n^2)$. I got confused about the DP stuff at the end of the question, so I was wondering if there is really any way to do it in $O(n \lg n)$ (or better), how do I build the optimal substructure in the case of DP?

• @DW well, it's from an interview question, no more information was given, in the last line it was said that I could use DP and if I use it, it should be O(nlogn), I think the last line was added just to make the examiner confused, I am not sure though. – ramgorur Aug 1 '13 at 22:38

A tip: this problem becomes much easier if you sort the $x$'s into increasing order. (If you sort by the $w$'s, your life will be much much harder.)

More precisely, you should sort the entries so the $x$-values are in increasing order, resolving ties so the $w$-values are in increasing order. This amounts to lexicographic order on $(x,w)$. This way, if $i<j$, then $x_i\le x_j$ and either $x_i<x_j$ or $w_i\le w_j$.

Once the elements are sorted in this way, you can solve this problem with a linear scan.

Just scan from left to right (i.e., from $i=1$ to $n$), keeping track of the sum of the weights seen so far (i.e., $w_1+w_2+\dots+w_i$). When this sum transitions from less than $1/2$ to greater than $1/2$, you've found the weighted median. At the very end, if there are multiple elements with the same $x$-value as the one you found, scan leftwards to find the first element with the same $x$-value as the one you initially found.

Running time: $O(n \lg n)$. It takes $O(n \lg n)$ time to sort, plus $O(n)$ time for the linear scan. No need for fancy dynamic programming.

• Keep in mind that we should sort on x value then on w value (not just x value). Meaning, when the x values are equal, sort such the weights will be sorted in ascending order, i.e. x = (1, 1), w = (1, 2) will be sorted as x = (1, 1), w = (1, 2), not x = (1, 1), w = (2, 1). – Bernhard Barker Aug 2 '13 at 7:29
• Ok, let's take a proper example - x = all 1s, w = 0.3, 0.5, 0.7. You sort them w = 0.7,0.5,0.3 (if weights don't matter), you can't pick any of those. – Bernhard Barker Aug 2 '13 at 22:36
• @Dukeling, OK, I see what you mean. Maybe a slightly better example: if the weights were $(0.1,0.1,0.8)$ and they had been sorted as $(0.8,0.1,0.1)$, then my algorithm would fail. I've edited my answer to reflect your comments. Thank you for the helpful suggestions! You were 100% right all along, of course; sorry it took me a while to understand your meaning. – D.W. Aug 3 '13 at 0:17

This answer assumes that you can't reorder the x's. Based on a clarification on the question, this does not seem to meet OP's requirements, but I thought I'd leave it here nonetheless.

I'm pretty sure this can be solved in $O(n)$.

• Construct a $minSoFar$ array storing the minimum so far from the left.
Constructed in $O(n)$ going from left to right.

• Construct a $maxSoFar$ array storing the maximum so far from the right.
Constructed in $O(n)$ going from right to left.

• Initialize $rightWeight$ as the sum of all the weights. Constructed in $O(n)$.

• Initialize $leftWeight$ to 0.

• For i = 1:n: (obviously $O(n)$)

• $rightWeight {-}{=} w_i$
• If all these conditions hold, we've found the position we're looking for:

• $x_i > minSoFar[i]$ (all elements to the left are smaller than $x_i$)
• $x_i <= maxSoFar[i]$ (all elements to the right are bigger than $x_i$)
• $rightWeight < 1/2$ and $leftWeight >= 1/2$
• $leftWeight {+}{=} w_i$

Total running time = $O(n+n+n+n)$ = $O(n)$