LeetCode 3086 - Minimum Moves to Pick K Ones

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sliding Window, Prefix Sum

Solution

Exploration

The reviewer identified a sign error in the swap argument, so the first task is to determine the correct monotonicity direction before rebuilding the proof.

For $n=1$, there is only one permutation, so the statement is trivial.

For $n=2$, take

$$x_1=5,\quad x_2=2,\quad y_1=4,\quad y_2=1.$$

The ordered pairing gives

$$(5-4)^2+(2-1)^2=1+1=2.$$

The swapped pairing gives

$$(5-1)^2+(2-4)^2=16+4=20.$$

Thus correcting the inversion decreases the sum from $20$ to $2$.

Now compute the algebra carefully. Compare

$$A=(x_1-y_1)^2+(x_2-y_2)^2$$

with

$$B=(x_1-y_2)^2+(x_2-y_1)^2.$$

Then

$$B-A=2(x_1-x_2)(y_1-y_2)\ge0.$$

Hence

$$A\le B.$$

The ordered arrangement is the smaller one. Therefore, when an inverted adjacent pair is swapped into correct order, the sum decreases or stays unchanged. The previous proof reversed this interpretation.

Test another example with repeated values:

$$x=(7,7,1),\qquad y=(5,5,0).$$

Every decreasing permutation equal to $(5,5,0)$ gives the same value. Equality can occur when adjacent entries are equal, since

$$2(x_i-x_{i+1})(z_{i+1}-z_i)=0.$$

For $n=3$, take

$$x=(5,4,1),\qquad z=(2,0,3).$$

There is an adjacent inversion because $0<3$. The current contribution at positions $2,3$ is

$$(4-0)^2+(1-3)^2=16+4=20.$$

After swapping:

$$(4-3)^2+(1-0)^2=1+1=2.$$

Again the swap decreases the sum.

The corrected strategy is now consistent:

Starting from an arbitrary permutation, repeatedly swap adjacent inverted pairs. Every swap decreases or preserves the sum. The process terminates at the decreasing arrangement $(y_1,\dots,y_n)$. Therefore the decreasing arrangement has the minimum value.

No contradiction remains.

Problem Understanding

We are given two decreasing sequences of real numbers,

$$x_1\ge x_2\ge\cdots\ge x_n, \qquad y_1\ge y_2\ge\cdots\ge y_n.$$

We must prove that among all permutations $(z_1,\dots,z_n)$ of the numbers $y_1,\dots,y_n$, the quantity

$$\sum_{i=1}^n (x_i-z_i)^2$$

is minimized when the $y_i$ are matched with the $x_i$ in the same decreasing order.

The reviewer correctly observed that the previous proof contained a critical sign mistake. The algebraic inequality itself was correct, but the proof incorrectly claimed that sorting adjacent inversions increases the sum. Explicit numerical tests show the opposite behavior. The corrected proof must track the direction rigorously.

Key Observations

The entire argument reduces to the case of two terms.

Suppose

$$a\ge b,\qquad c\ge d.$$

Then compare the ordered pairing

$$(a-c)^2+(b-d)^2$$

with the crossed pairing

$$(a-d)^2+(b-c)^2.$$

Their difference is

$$(a-d)^2+(b-c)^2-(a-c)^2-(b-d)^2 =2(a-b)(c-d)\ge0.$$

Hence

$$(a-c)^2+(b-d)^2 \le (a-d)^2+(b-c)^2.$$

Now consider a permutation $z_1,\dots,z_n$. If some adjacent pair satisfies

$$z_i<z_{i+1},$$

then that pair is out of decreasing order. Swapping those two entries replaces

$$(x_i-z_i)^2+(x_{i+1}-z_{i+1})^2$$

$$(x_i-z_{i+1})^2+(x_{i+1}-z_i)^2.$$

Applying the two-variable inequality with

$$a=x_i,\quad b=x_{i+1},\quad c=z_{i+1},\quad d=z_i,$$

shows that the swapped arrangement is smaller or equal.

Thus every adjacent inversion can be corrected without increasing the sum.

Repeatedly correcting inversions eventually produces the decreasing arrangement

$$(y_1,\dots,y_n),$$

because inversion count strictly decreases at every nontrivial swap.

Solution

Lemma 1. If

$$a\ge b \qquad\text{and}\qquad c\ge d,$$

then

$$(a-c)^2+(b-d)^2 \le (a-d)^2+(b-c)^2.$$

Proof.

Compute

\begin{align*}

&(a-d)^2+(b-c)^2-(a-c)^2-(b-d)^2 \

(a^2-2ad+d^2+b^2-2bc+c^2) \

&\quad-

(a^2-2ac+c^2+b^2-2bd+d^2) \

2ac+2bd-2ad-2bc \

2(a-b)(c-d).

\end{align*}

Since

$$a-b\ge0 \qquad\text{and}\qquad c-d\ge0,$$

the difference is nonnegative. Hence

$$(a-c)^2+(b-d)^2 \le (a-d)^2+(b-c)^2.$$

∎

Lemma 2. Let $(z_1,\dots,z_n)$ be a permutation of $(y_1,\dots,y_n)$. Suppose that for some index $i$,

$$z_i<z_{i+1}.$$

Let $(z_1',\dots,z_n')$ be obtained by swapping $z_i$ and $z_{i+1}$. Then

$$\sum_{j=1}^n (x_j-z_j')^2 \le \sum_{j=1}^n (x_j-z_j)^2.$$

Proof.

Only the terms at indices $i$ and $i+1$ change. Therefore it suffices to compare

$$(x_i-z_i)^2+(x_{i+1}-z_{i+1})^2$$

with

$$(x_i-z_{i+1})^2+(x_{i+1}-z_i)^2.$$

Since

$$x_i\ge x_{i+1} \qquad\text{and}\qquad z_{i+1}\ge z_i,$$

Lemma 1 gives

$$(x_i-z_{i+1})^2+(x_{i+1}-z_i)^2 \le (x_i-z_i)^2+(x_{i+1}-z_{i+1})^2.$$

Thus the swap does not increase the total sum.

∎

Now let $(z_1,\dots,z_n)$ be any permutation of $(y_1,\dots,y_n)$.

$$z_1\ge z_2\ge\cdots\ge z_n,$$

then, because the numbers $z_i$ are exactly the numbers $y_i$ arranged in decreasing order,

$$z_i=y_i \quad\text{for all }i.$$

Otherwise, there exists an index $i$ such that

$$z_i<z_{i+1}.$$

Apply Lemma 2 to swap this adjacent inversion. The total sum does not increase.

Continue this process. Every nontrivial adjacent swap decreases the number of inversions by $1$, so after finitely many steps the process terminates. The terminal sequence has no adjacent inversion, hence is decreasing. Therefore the terminal sequence is

$$(y_1,\dots,y_n).$$

At every step the sum weakly decreases, so the final value is at most the initial value:

$$\sum_{i=1}^n (x_i-y_i)^2 \le \sum_{i=1}^n (x_i-z_i)^2.$$

This completes the proof.

∎

Verification of Key Steps

The reviewer’s critical objection concerned the monotonicity direction in the swap argument. The corrected proof resolves this by tracking explicitly which configuration is ordered and which is unordered.

Take

$$x=(5,2),\qquad z=(1,4).$$

The adjacent pair is inverted because $1<4$. Before swapping,

$$(5-1)^2+(2-4)^2=20.$$

After swapping,

$$(5-4)^2+(2-1)^2=2.$$

Hence correcting the inversion decreases the sum, exactly as Lemma 2 now states.

The termination argument also requires verification. Each adjacent swap removes one inversion from the permutation. Since the inversion count is a nonnegative integer, the process must stop after finitely many swaps. The only permutations with no adjacent inversions are decreasing sequences, so the final arrangement is the ordered sequence $(y_1,\dots,y_n)$.

Equality cases are consistent with the formula

$$2(a-b)(c-d).$$

Equality occurs precisely when either

$$a=b$$

$$c=d.$$

Thus repeated equal values in either sequence naturally produce nonunique minimizing swap paths while preserving the same final minimum.

Alternative Approaches

Another proof expands the squares:

\begin{align*}

\sum_{i=1}^n (x_i-z_i)^2

\sum_{i=1}^n x_i^2

\sum_{i=1}^n z_i^2

2\sum_{i=1}^n x_i z_i.

\end{align*}

Because $(z_i)$ is a permutation of $(y_i)$,

$$\sum z_i^2=\sum y_i^2.$$

Hence minimizing

$$\sum (x_i-z_i)^2$$

is equivalent to maximizing

$$\sum x_i z_i.$$

The rearrangement inequality states that for two decreasing sequences,

$$\sum_{i=1}^n x_i y_i$$

is the maximum possible value among all permutations of the $y_i$. Therefore

$$\sum_{i=1}^n (x_i-y_i)^2$$

is the minimum possible squared-distance sum.

This argument is shorter, but it relies on the rearrangement inequality as an external theorem. The adjacent-swap proof establishes the result directly from elementary algebra.