1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – ramgorur Aug 1 '13 at 22:38
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Dukeling Aug 2 '13 at 7:29
  • $\begingroup$ 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. $\endgroup$ – Dukeling Aug 2 '13 at 22:36
  • $\begingroup$ @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. $\endgroup$ – D.W. Aug 3 '13 at 0:17
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.