A complicated variant of Weighted Median problem

Question

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?

Answer 1

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.

---

My thanks to Dukeling for helpful comments and corrections!

Answer 2

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)$