Subtracting Arrays

Question

What's a fastest way to implement array subtraction? For example:

array a1 = [1, 3, 4, 5, 8];
array a2 = [2, 4, 5];

array a3 = a1 - a2; /* [1, 3, 8] */

Here array would be the type my program uses to represent a struct which is used as a container. The rest of it is pseudo code, of course I'm not creating the arrays like that nor subtracting.

The simplest solution I can think of involves nested loops:

/* a1 - a2 */
for (i = 0; i < a1.size; ++i) {
    int is_the_same = 0;
    for (j = 0; i < a2.size; ++j)
        if (a1[i] == a2[j]) {
            is_the_same = 1;
            break;
        }
    }
    if (!is_the_same)
       a3.push a1[i];
}

But this does not look very efficient. What would be another approach?

Answer 1

If your arrays aren't sorted, the worst case time complexity for an array exclusion using a intuitive solution is O(n²) (although you can boost this if you sort the arrays first), since you need to check the whole array whether an element is existent or not.

Example of worst case scenario:

array a1 = [1, 3, 4, 5, 8];
array a2 = [8, 5, 4, 3, 1];

If your arrays are ordered, then the worst case time complexity is O(n+m) (pseudo-code):

int i = 0;
for(int j = 0; i < a1.size && j < a2.size;){
    if(a1[i] == a2[j])
        ++i, ++j;  // exclude this element
    if(a1[i] < a2[j]){
         a3.push(a1[i]); // include this element
         ++i;
    }
    if(a1[i] > a2[j])
         ++j; // ignore lesser elements
}
while(i < a1.size)
     a3.push(a1[i]);

UPDATE -Wall -Wextra -pedantic C code:

#include <stdio.h>
#include <malloc.h>

/**
* The following function excludes values from an array using another arrays values.
* Note that this version won't exclude multiple values, for this you have to drop
* '++j' in line 25.
*
* \param[in] from Original sorted array
* \param[in] from_length Original array length
* \param[in] what Sorted array including the excluding values
* \param[in] what_length self describing
* \param[out] result_length the lenght of the new array - a value lesser 0 indicates an error.
*/

int* exclude(int* from, int from_length, int* what, int what_length, int* result_length){
    int i,j,k;
    int* result = (int*) malloc(sizeof(int)*from_length);
    if(result == NULL){
        *result_length = -1;
        return NULL;
    }
    for(i = j = k = 0; i < from_length && j < what_length;){
        if(from[i] == what[j])
            ++i, ++j;  /* exclude this element - to enable multiple exclusion drop '++j' 
                        4,4,5,6 /4 --> 5,6 */
        if(from[i] < what[j])
            result[k++] = from[i++];
        if(from[i] > what[j])
             ++j; /* ignore lesser elements */
    }
    while(i < from_length)
        result[k++] = from[i++];

    if( k < from_length){
        int* tmp = (int*) realloc(result,sizeof(int)*k);
        if(tmp == NULL){
            /* either error handling or returning result */
        }else{
            result = tmp;
        }
    }
    *result_length = k;
    return result;
}

int main(){
    int a[6] = {1,2,3,4,5,6};
    int b[3] = {2,4,5};
    int result_length;
    int i;
    int *c = exclude(a,6,b,3,&result_length);
    for(i = 0; i < result_length; ++i)
        printf("%i ",c[i]);
    free(c);
    return 0;
}

This will result in a worst time complexity of O(n+m) for sorted arrays and O(n log n + m log m) for non-sorted arrays (sort both, use the function provided above).