Compare two sorted arrays and find missing elements between them-CodePudding

I have two arrays that are lexically sorted:

Array1 is a kind of sorted superset of Array2 that is all the elements in Array2 will also be in Array1 but not vice versa.

Array1: [A,B,C,D,E,F,G]

Array2: [B,C,F]

Result: [A,D,E,G]

The result will have the missing elements not present in Array2 but in Array1.

I am looking for the best optimal solution.

One of my logic was to use a binary search but I am stuck thinking about how to implement it.

Any help on a correct algorithm would be great.

Edit: Duplicates are allowed.

CodePudding user response：

This O(n) and can be achieved by iterating through the superset while keeping a pointer to the most recently matched element in the subset and noting which superset elements are absent from the subset.

An implementation in C#:

char[] superset = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
char[] subset = new char[] { 'B', 'C', 'F' };

List<char> missing = new List<char>();
int subIdx = 0;
foreach (var element in superset)
{
    if (subIdx < subset.Length && subset[subIdx] == element)
        subIdx  ;
    else
        missing.Add(element);
}

var result = missing.ToArray(); // If you need an array rather than list

CodePudding user response：

Python reference implementation by using set:

L1 = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
L2 = ['B', 'C', 'F']
print(set(L1) - set(L2))
# {'A', 'E', 'G', 'D'}