Efficient algorithm for difference of array and a known subsequence?

Question

I'm passing an array to a library function which returns an array which is a subsequence of the input array. That is to say the orders of the first and second array are identical but the second array may be lacking any number of elements of the first array. There will be no duplicates in either array!

I want to then build a new array of all the elements which were in the input but are not in the output of the function.

For some reason though it sounds trivial I keep getting it wrong, especially at the ends of the arrays it seems.

Example 1 (typical):

input array a:

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, ios, app, tlv, lcy ]

input array b:

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, tlv, lcy ]

output array "diff":

[ ios, app ]

Example 2 (minimal, reveals some bugs when the difference is at the end of the strings):

input array a:

[ usa ]

input array b:

[ ]

output array "diff":

[ usa ]

(I'm going to implement it in JavaScript / jQuery but I'm more interested in a generic algorithm in pseudocode since I'll actually be dealing with arrays of objects. So please I'm looking for algorithms which specifically use array indexing rather than pointers like I would in C/C++)

Answer 1

As the second array b is a subset of the first array a with the same order, you can walk both in parallel, compare the current values, and take the current value of a if it is different from the current value of b:

var a = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','ios','app','tlv','lcy'],
    b = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','tlv','lcy'],
    diff = [];
var i=0, j=0, n=a.length, m=b.length;
while (i<n && j<m) {
    if (a[i] !== b[j]) {
        diff.push(a[i]);
    } else {
        j++;
    }
    i++;
}
while (i<n) {
    diff.push(a[i++]);
}

Or if you prefer just one while loop:

// …
while (i<n) {
    if (j<m && a[i] === b[j]) {
        j++;
    } else {
        diff.push(a[i]);
    }
    i++;
}