Skip to main content

New answers tagged

5 votes

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 ...
gnasher729's user avatar
  • 30.7k
6 votes
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 ...
EnEm's user avatar
  • 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 ...
codeR's user avatar
  • 1,467
3 votes
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 $. ...
Lisa E.'s user avatar
  • 538
-1 votes

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

You can formulate this problem as a weighted version of maximum bipartite matching problem. For each element $a_i$, create a vertex $u_i$, and for element $b_j$, create a vertex $v_j$. Let us define $...
codeR's user avatar
  • 1,467
1 vote

Algorithm to sort array into K increasing subsets?

First, consider the case when $k$ is a perfect power of $2$. You find the median of the input array in $O(n)$ time using the Selection algorithm. Now take the median as the pivot to partition the ...
codeR's user avatar
  • 1,467
0 votes

Selecting a subtree in an array representation of a binary tree

@Bulat descendant >> (hsbit(descendant) - hsbit(ancestor)) == ancestor This does not appear to work for descendant = 2 (0b10), ...
Minh Tran's user avatar

Top 50 recent answers are included