<p>You are given two <strong>0-indexed</strong> arrays <code>nums</code> and <code>cost</code> consisting each of <code>n</code> <strong>positive</strong> integers.</p>

<p>You can do the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Increase or decrease <strong>any</strong> element of the array <code>nums</code> by <code>1</code>.</li>
</ul>

<p>The cost of doing one operation on the <code>i<sup>th</sup></code> element is <code>cost[i]</code>.</p>

<p>Return <em>the <strong>minimum</strong> total cost such that all the elements of the array </em><code>nums</code><em> become <strong>equal</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,5,2], cost = [2,3,1,14]
<strong>Output:</strong> 8
<strong>Explanation:</strong> We can make all the elements equal to 2 in the following way:
- Increase the 0<sup>th</sup> element one time. The cost is 2.
- Decrease the 1<sup><span style="font-size: 10.8333px;">st</span></sup> element one time. The cost is 3.
- Decrease the 2<sup>nd</sup> element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2,2,2], cost = [4,2,8,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All the elements are already equal, so no operations are needed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length == cost.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], cost[i] &lt;= 10<sup>6</sup></code></li>
	<li>Test cases are generated in a way that the output doesn&#39;t exceed&nbsp;2<sup>53</sup>-1</li>
</ul>

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:

        arr = sorted(zip(cost, nums))
        totalcost = sum(cost)

        #count = totalcost//2
        cost = 0 
        
        for c, num in arr:    
            cost+=c
            if cost>totalcost//2:
                target = num
                break


        return sum(c*abs(target-num) for c, num in arr)


















































    # weighted median
    # onlogn and space is 0(n)
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        arr = sorted(zip(nums, cost))
        total, cnt = sum(cost), 0
        for num, c in arr:
            cnt += c
            if cnt > total // 2:
                target = num
                break
        return sum(c * abs(num - target) for num, c in arr)

    """
Question1: Why median?
    Because we are minimizing the L1 distance (i.e. weighted sum of absolute values), the answer is the weighted median. If, however, we want to minimize the L2 distance (i.e. weighted sum of squares), then the answer is the weighted mean. Under the hood, this is a math problem. See this post for more discussions.
https://math.stackexchange.com/questions/1547336/minimizing-the-sum-of-weighted-absolute-distance

    Question 2: Why cnt > total // 2 instead of cnt >= total // 2
Question 2: Let's say iftotal = 4 which is an even number, then either the 2nd or the 3rd ordered number (in the collapsed array) could be the weighted median, so we take the first order element with cumulative frequency greater than 4 // 2 = 2 to be the target (i.e. the 3rd order number); iftotal = 5 which is an odd number, then only the 3rd ordered number (in the collapsed array) could be the weighted median, so we take the first order element with cumulative frequency greater than 5 // 2 = 2 to be the target (i.e. the 3rd order number).

    Question 3: Why target is one of the elements in the array? for example nums = [1, 2 5, 7], why target cannot be 4 or something else?

Question 3: For this weighted median approach, we actually don't need to know whether target is one of the elements in the array or not. However, the underlying math guarantees that target has to be one of the elements in array to reach the minimum cost. For a short (heuristic) justification, please see @votrubac's post on Pivot.

    """
286