HuangJie HuangJie - 1 month ago 8
C Question

find the unmatched elements at each index in two arrays

Suppose I have two arrays below (same length), the array is not sorted (randomly):

a[] = {1, 3, 5, 7, 10, 11}
b[] = {1, 4, 5, 7, 9, 11}


May I know what's the fastest way to find all the unmatched (different) values between these two arrays? (the index information is enough). Many thanks for your time.

Answer

If you are only interested in the indices which correspond to cells with different values in arrays a and b, just iterating through both arrays and checking whether their indices are equal would be sufficient. The parameter N given below indicates the size of the arrays a and b.

int get_unmatched_indices(int a[], int b[], int N, int indices[])
{
    int i, num_unmatched = 0;
    for(i = 0; i < n; ++i)
    {
        if (a[i] != b[i])
        {
            indices[num_unmatched++] = i;
        }
    }
    return num_unmatched;
}

The function above finds out the information you seek using O(N) extra space (for the indices) and O(N) time. If you then want to print the unmatching elements at the found indices, you can iterate over indices and print the values of each a[indices[X]] and b[indices[X]].

Explanation on whether a better efficiency could be achieved:

Any approach depending on comparing the values of the elements in a and b require you to read each element in a and b. This can trivial to prove by contradiction. Assume that you can skip comparing the values of a[i] and b[i] at an index i. Then, there is no way of you to know whether a[i] and b[i] are unmatched elements or not, as an indispensable bit of information is skipped.

Now, there are certain problem categories where some approaches better than comparison-based algorithms exist. Sorting is an example. There are comparison-based sorting algorithms, which are at best O(NlogN), but there are also other algorithms that have O(N) complexity, with other certain restrictions. So, theoretically it may seem as if there is some non-comparison-based approach that could work. However, even in those algorithms, you would at least need to process all the essential information. (i.e. traverse each element and process it to some form) So even then you already reach to O(N) complexity. So any algorithm you may devise could provide a constant factor of efficiency, at best.

Comments