# Tag Info

## New answers tagged arrays

### Arrays. Find row with most 1's, in O(n)

Hint: If the first row has k 1s, and the second row has k’ 1s, then there is no need to determine k’ at all if k’ <= k. How do you find in O(1) that k’ <= k? And if k’ > k, which you checked ...
• 30.7k
Accepted

### Arrays. Find row with most 1's, in O(n)

Below is an algorithm which runs in $\mathcal{O}(1)$ memory and $\mathcal{O}(n)$ time. It accepts a $n \times n$ matrix $A$ which is $1$-indexed, follows the constraint described in the problem, and ...
• 381
1 vote

### Prove that the L1 distance between two arrays is minimized when both are sorted

Yes, two sorted sequences will always give you the minimum $l_1$ distance. Suppose that is not the case. Without loss of generality, assume that all $a_i$s are sorted but $b_i$s aren't. So there must ...
• 1,467
Accepted

### Prove that the L1 distance between two arrays is minimized when both are sorted

Prove the lemma for arrays in two dimensions. That is, show that if $a_1 > a_2$ and $b_1 > b_2$, then $\vert a_1-b_1\vert + \vert a_2-b_2\vert < \vert a_2-b_1\vert + \vert a_1-b_2\vert$. ...
• 538