1

We know two arrays A, B of size n have same set of distinct integer values, but maybe ordered in different ways, so there is one-to-one match between the two arrays. We don't know the actual values stored in the arrays, and no way to access values of the array thus can't use function such as sorted. However we may ask question about any pair of A[i] and B[j], and get answer of whether A[i] = B[j], A[i] > B[j] or A[i] < B[j].

What's an efficient algorithm to match each element A to its corresponding element in B? First thing came to my mind is a simple brute force approach, first match A[1] with its counterpart in B by repeated asking relationship question between A[1] and B[j] for j = 1 to n until we find the match. Then do the same for A[i] for i = 2 to n to find match for rest of the A[i]s. The worst case running time would be n + (n - 1) + ... + 1 = O(n^2). But seems this would not be the most efficient way to do it, because we only used the information of whether A[i] = B[j], but not the more detailed information of whether A[i] > B[j] or A[i] < B[j]. Intuitively there should be a way to utilize the relative order between A[i] and B[j] to design an algorithm in less than O(n^2) time.

Any help would be greatly appreciated!

Improve this question

4 Answers 4

Reset to default
4

Since you can't compare elements in the same array, you can't sort them individually, but you can do a sort of mutual quicksort, still in expected O(N log N) time:

  1. Pick an element of A as the A-pivot
  2. Partition the elements of B according to how they compare to the A-pivot. One of them will compare equal. That is the B-pivot
  3. Partition the elements of A according to how they compare the the B-pivot. The partitions will be the same sizes as B's partitions if there's a 1-1 matching.
  4. Recurse on the lower A and B partitions, and the upper A and B partitions.
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Had some fun implementing this.
Hi @Matt, thanks so much for your answer, that's exactly what I wanted, and you explained it clearly!
1

Here's my attempt on this problem:

from collections import defaultdict
a = [1,2,4,5,8]
b = [8,5,4,1,2]
d = defaultdict(list)   #(element,index) map

for i,v in enumerate(a):
    d[v]=[i]
for j,x in enumerate(b):
    d[x].append(j)
print(d)

Pretty straightforward.I'm creating a element to index map for one array, and using it match the keys of second array.
Time Complexity: O(n) Space Complexity: O(n)
Trying to find a O(1) space complexity solution, which intuitively could be done using divide and conquer approach, making use of that specified query we can ask for each element. Will update soon.

Improve this answer

1 Comment

Thanks for replying. Hivert is right, maybe I didn't state it clear enough. We don't have numerical value on any of the elements, thus no sorting is available. We can only compare them pairwise, and get relative order of the pair.
1

The OP question is not so clear. First he says that the entries are integers but then he says that he can only compare them 2 by 2, which suggest that he cannot hash them. Here is a solution if hashing is not possible:

I would sort both array keeping the position of the elements along the elements. You can then check if the sorted values are equal and find the matching thanks to the positions. It is O(n log(n))

val1 = ["1", "5", "3", "6"]
val2 = ["3", "6", "1", "5"]

//  Key = ... means to compare i and j, compare val1[i] with val2[j]
val1s = sorted(range(len(val1)), key = lambda i: val1[i])
// The result is
val1s
[0, 2, 1, 3]
// which is effectively the order in which val1 must be read to have it sorted...

val2s = sorted(range(len(val2)), key = lambda i: val2[i])

perm = [None]*len(val1)
for i in range(len(val1)):
    perm[val1s[i]] = val2s[i]
    
perm

[2, 3, 0, 1]

Note : the code works verbatim with anything with is comparable (eg: strings).

Edit : I'm answering to the comment "you can't sort the array, since you don't know the array elements". This is wrong in some sense. Instead of sorting the array (I'm not allowed to change it), I return a list which give the correct order to read the array to be sorted. It is perfectly possible to get that without accessing to the element. See the python code.

Improve this answer

12 Comments

Thanks for replying, maybe I didn't state it clear enough. We don't have numerical value on any of the elements, thus no sorting is available. We can only compare them pairwise, and get relative order of the pair.
Sorry but this doesn't make sense for me. You can sort anything which is comparable ! Not only numbers but for example strings, poker cards...
Ok, maybe I should phrase it this way, this is no way we can access actual values of the array. The only information we can get is the relative order of any pair A[i] and B[j], then we match the 2 arrays based on that information alone.
@hivert you can't sort the array, since you don't know the array elements
@hivert you aren't given val1 and val2
|
1

Here's a Python implementation of Matt's algorithm.

  • AB creates and hides A and B, only offering to compare A[i] and B[j] and checking whether index lists I and J are a perfect match.
  • quickmatch is the solution algorithm

Demo outupt showing the computed I, J and whether they're a perfect match:

[16, 0, 19, 7, 10, 15, 12, 14, 5, 4, 11, 18, 1, 9, 2, 6, 13, 8, 3, 17]
[1, 3, 13, 12, 0, 18, 9, 4, 14, 17, 11, 6, 5, 7, 15, 2, 8, 10, 16, 19]
True

Code:

from random import shuffle

class AB:
    def __init__(self, n):
        A = list(range(n))
        B = list(range(n))
        shuffle(A)
        shuffle(B)
        def cmp(i, j):
            a = A[i]
            b = B[j]
            return -1 if a < b else 1 if a > b else 0
        def check(I, J):
            if not (sorted(I) == sorted(J) == list(range(n))):
                return False
            return all(A[i] == B[j] for i, j in zip(I, J))
        self.cmp = cmp
        self.check = check

def quickmatch(I, J):
    if not I:
        return I, J

    ipivot = I[0]
    jpivot = next(j for j in J if ab.cmp(ipivot, j) == 0)

    small_I = [i for i in I if ab.cmp(i, jpivot) < 0]
    small_J = [j for j in J if ab.cmp(ipivot, j) > 0]
    small_I, small_J = quickmatch(small_I, small_J)

    large_I = [i for i in I if ab.cmp(i, jpivot) > 0]
    large_J = [j for j in J if ab.cmp(ipivot, j) < 0]
    large_I, large_J = quickmatch(large_I, large_J)

    return (small_I + [ipivot] + large_I,
            small_J + [jpivot] + large_J)

# Create a test case
n = 20
ab = AB(n)

# Solve
I = list(range(n))
J = list(range(n))
I, J = quickmatch(I, J)

# Check
print(I)
print(J)
print(ab.check(I, J))
Improve this answer

1 Comment

thanks for implementing Matt's algorithm, by creating both explicit code and the testing function. Glad that you had some fun doing this!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.