1
$\begingroup$

I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted.

Example Inputs: A = [2,5,1,8], B = [9,3,6,10]

Expected Outputs: A = [2,5,1,3], B = [9,8,6,10]

I solved using brute force way that takes O(n^2) but I am wondering if it can be solved in a better way in terms of time complexity?

$\endgroup$
4
  • $\begingroup$ You might want to add "two unsorted arrays... of the same number of elements" to your question to exclude the trivial case. It's a good question because a initial thought of "sort the two arrays, then walk them comparing entries" may be inferior to sorting the first array then as elements of the second array are sorted then return false if two elements which should match fail to do so. This modification may end up preferring a normally sub-optimal sort algorithm and achieve a better average case than O(n + 2n.log(n)), maybe O(1.5n.log(n)). $\endgroup$
    – vk5tu
    Oct 8 at 0:45
  • $\begingroup$ (If equality was allowed, there's a trivial linear solution.) $\endgroup$
    – greybeard
    Oct 8 at 6:47
  • $\begingroup$ Do you require the result to be stable, in the sense that the original ordering of elements is preserved? $\endgroup$
    – rici
    Oct 8 at 15:50
  • $\begingroup$ Also, I think the word "compare" in the question title is misleading. You don't want to compare the two arrays, which are obviously not going to be the same. You're trying to do a minimal reordering. $\endgroup$
    – rici
    Oct 8 at 16:22
2
$\begingroup$

You can use quickselect, which has expected linear time complexity. (There's a version using the median-of-medians partitioning algorithm which has worst-case linear time complexity, but it's usually a lot slower in practice.) Note that if there are duplicate elements in the two arrays, it might not be possible to satisfy the strict less-than constraint without modifying the lengths of the two result arrays.

A simple in-place quickselect solution would be to consider the two input arrays $A$ and $B$ as a single contiguous array $\overline{AB}$ by using the indexing function

$$\begin{equation}\overline{AB}_i = \begin{cases}A_i, &\text{ if }i\le|A|\\ B_{i-|A|}, &\text{ otherwise } \end{cases} \end{equation} $$

You then run quickselect on $\overline{AB}$ for element $|A|+1$. (That assumes that indexing starts at 1. If you're used to 0-based indexing, adjust as necessary.) This takes expected time $O(|A|+|B|)$ and does not require $A$ and $B$ to be the same length.

If you require the outputs to be stable, as shown in your example (so that the elements in each output array preserve their original order from the original arrays), then you can use quickselect as above to find $p=\text{element }|A|+1\text{ of }\overline{AB}$, as above, but working on a copy of the concatenation of the two arrays (because quickselect is an in-place algorithm which modifies its input). You then do a final $O(|A|+|B|)$ scan over the two arrays simultaneously, looking for an element in $A$ which is greater than $p$ and an element in $B$ which is less than $p$. Swap these two elements and continue the scan. (If duplicate elements are allowed and $p$ happens to be a duplicate, then some adjustment will be needed.)

$\endgroup$
1
$\begingroup$

You could sort them and then iterate over them. Sorting is $n\log n$ and then it would only take one more pass to go check them because once you've passed an element, you know you've done all the swapping you need for that element.

$\endgroup$
1
  • $\begingroup$ (Care to work out where "min-heapifying" both and afterwards moving elements just where necessary gets one?) $\endgroup$
    – greybeard
    Oct 8 at 6:52
-1
$\begingroup$

Concatenate A and B into one array C with a total length of 2n. You start with the partition [1, 2n] of C with the goal to make the first l items less than the last r items, l = r = n initially.

As long as your partition has length 2 or more: Pick a random pivot element. Partition into two partitions of length x and y, like in quick sort. If x <= l then you remove the first x items from the partition, and subtract x from l. If y <= r then you remove the last y items from the partition and subtract y from r. Since x+y = l+r, either x <= l or y <= r must be true; both if you are lucky. So you repeat until the length of the remaining partition is 1, and you are done.

Proof of correctness: At each step, the items left of the partition are smaller than the ones inside or to the right of the partition, and the ones right of the partition are greater than the ones inside or to the left of the partition.

Average time is O(n).

And must have gone straight over someone's head :-)

$\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.