Interleave two unsorted arrays to get the lexicographically maximal result

user_481267 0
Viewed 94

Suppose we have two unsorted arrays, A[1...m] and B[1...n]. The objective is to return an array C[1...(m+n)] formed by interleaving the elements from A and B (in other words, A[i] must precede A[i+1] and B[i] must precede B[i+1] in C) such that C is as large as possible in lexicographical order. What are some approaches to solve this problem in linear time?

The basic approach is greedy: if A[i] is bigger than B[j], then take A[i] and increment i, or else if B[j] is bigger than A[i] then take B[j] and increment j. The difficulty arises when A[i] and B[j] are equal. In this case we have to "look ahead" to find the first position k such that A[i+k] and B[j+k] differ. The code in C++ looks like this:

// A, B are the input vectors
vector<int> C;
auto it1 = A.begin();
auto it2 = B.begin();
while (it1 != A.end() || it2 != B.end()) {
    if (std::lexicographical_compare(it1, A.end(), it2, B.end())) {
        C.push_back(*it2++);
    } else {
        C.push_back(*it1++);
    }
}

Because of the requirement to look ahead, this can take quadratic time.

One approach to do it in linear time is to concatenate the two arrays with a separator that is guaranteed to compare less with all elements of the original arrays, compute the suffix array of this combined array, and use that in order to easily look up which suffix is greater instead of doing a full scan in every iteration of the while loop.

  • As suffix array construction is relatively complicated, I am interested in whether simpler approaches exist.
  • In addition, a suffix array uses linear extra memory and I am wondering whether there is a solution that takes linear time and only uses constant extra memory. (By this I mean that the memory occupied by the output array C doesn't count toward the limit, but you are only allowed to append to C, and thereafter may not go back to read or write any previous elements of C.)
algorithm
1 Answers

I'm just going to describe the partial algorithm that I have in pseudocode.

First of all the trivial cases.

if (it1 == A.end()) {
    copy from it2 until end
}
else if (it2 == A.end()) {
    copy from it1 until end
}
else if (*it1 < *it2) {
    copy one value from it1
}
else if (*it2 < *it1) {
    copy one value from it2
}
else {
    // This is where it gets tricky
    scan_forward(A, B, C, it1, it2)
}

Now the idea of scan_forward is that we find a way to scan forward, then take a big giant block of values. This should take very little overhead if done right. But "if done right" is tricky and I haven't figured it all out yet. Still the idea is this.

it1_scan = copy of it1
it2_scan = copy of it2
while true {
    if (it1_scan == A.end()) {
        if (it2_scan == A.end() or  *it1 < *it2_scan) {
            copy it1 over
            copy it2 over
        }
        else if (*it1 == *it2_scan)  {
            scan forward on it2_scan
            if you find the end first or it2_scan finds something larger than *it1 {
                copy it1 over
                copy it2 over
            }
            else {
                copy it2 over until it2_scan's lower
                return and proceed
            }
        else {
            copy it2 until it2_scan
            return and proceed.
        }
    else if (it2_scan == B.end()) {
        Mirror logic for it2_scan knowing that it1_scan is not (yet) end.
    }
    else if (*it1_scan < *it2_scan) {
        copy it1 until it1_scan
        return and proceed.
    }
    else if (*it2_scan < *it1_scan) {
        copy it2 until it2_scan
        return and proceed.
    }
    else if (*it1 < *it1_scan) {
        copy it1 until it1_scan
        copy it2 until it2_scan
        return and proceed.
    }
    else {
       This is what I have not worked out.
       We want to do one of:
          - drain it1 and keep going
          - drain it2 and keep going
          - drain it1 then it2 then decide what to do.
    }

}

I began writing that complicated bit out and found that I have 3 courses to follow in parallel. And a lot of options. I did not work that out in detail, but it does seem that options do not multiply. However you do get into a weird state where you know you want to do some of one, then backtrack and do some of the other. But you have not yet decided which to copy first. That piece of logic can go on surprisingly long, but I think only with bounded overhead.

However I confess to not working that part out in any detail.

user_5854110
Related