Finding the intersection of two sets of integers

Question

I need to pass a programming exam in order to graduate but I'm having a hard time passing it because most of my programs are too slow. Can someone give me some tips on how to make my programs faster please? Below is an example of a question we had in the last exam and the code i wrote. My code passed the first test case but for the other 3 it exceeded the time limit. Please let me know if you have any suggestions on how to improve my code.

Description
Given two sets of numbers, output their intersection set.

Input
There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set.

All the numbers are 32 bit signed integers.

The input is terminated if N = 0.

For case 1, 1 <= N, M <= 10^3 (Time Limit: 1 sec)
For case 2, 1 <= N, M <= 10^4 (Time Limit: 1 sec)
For case 3, 1 <= N, M <= 10^5 (Time Limit: 1 sec)
For case 4, 1 <= N, M <= 10^6 (Time Limit: 3 sec)

Output
For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print 「empty」 (without quotes).

Sample Input
3
1 2 3
3
4 5 6
8
4 10 13 8 9 2 1 5
4
4 2 3 1
5
1 2 2 3 2
5
1 2 2 3 1
0

Sample Output
empty
1 2 4
1 2 2 3

This is my code:

#include<stdio.h>
#include<stdlib.h>

int set1[2][1000000];
int set2[2][1000000];
int intersection[1000000];

int main()
{
    int n;
    scanf("%d",&n);

    while( n!= 0)
    {
        int m, i, x, num, y = 0;
        int w, u, xx;

        for(i = 0; i < n; i++) //initialise set1 to 0
        {
            set1[1][i] = 0;
        }

        for(x = 0; x < n; x++) //put set1 in array
        {
            scanf("%d", &num);
            set1[0][x] = num;
        }

        scanf("%d",&m);
        for(i = 0; i < m; i++) //initialise set2 to 0
        {
            set2[1][i] = 0;
        }

        for(x = 0; x < m; x++) //put set2 in array
        {
            scanf("%d", &num);
            set2[0][x] = num;
        }

        for(x = 0; x < n; x++)
        {
            for(i = 0; i < m; i++)
            {
                if((set1[1][x] == 0) && (set1[0][x] == set2[0][i]) && (set2[1][i] == 0))
                {
                    intersection[y] = set2[0][i];//put in printing array
                    y++;
                    set2[1][i] = 1;
                    set1[1][x] = 1;
                }
            }
        }

        for(x = 0; x < y; ++x) //sort
        {
            for(i = x + 1; i < y; ++i)
            {
                if(intersection[x] > intersection[i])
                {
                    w = intersection[x];
                    intersection[x] = intersection[i];
                    intersection[i] = w;
                }
            }
        }

        for(x = 0; x < y; x++)//print
        {
            if(x == 0)
            {
                printf("%d", intersection[x]);
            }
            else printf(" %d", intersection[x]);
        }

        if (y == 0)
        {
            printf("empty");
        }
        printf("\n");

        scanf("%d",&n);
    }
    return 0;
}

Answer 1

Let's look at these two nested loops. How many times does the loop body need to be executed?

for(x = 0; x < n; x++)
{
    for(i = 0; i < m; i++)
    {
        /* loop body ... */
    }
}

The loop body gets executed \$ nm \$ times. But the problem statement says that we have \$ 1 \le n, m \le 10^6 \$, so in the worst case \$ n = m = 10^6 \$ and so the loop body gets executed \$ 10^{12} \$ times. There's no way to do that in just 3 seconds!

So you need to find a different algorithm, one that doesn't try to examine every pair of elements.

How might you do that? Well, here are two ideas:

1. Sort the two arrays, and then output the intersection by merging the sorted arrays.

2. Store the first input set in a data structure that has efficient lookup, for example a hash table or a radix tree, and then look up the numbers in the second input set.

Answer 2

First use pre-increment.

This:

for(i = 0; i < n; i++) //initialise set1 to 0
{
    set1[1][i] = 0;
}

for(x = 0; x < n; x++) //put set1 in array
{
    scanf("%d", &num);
    set1[0][x] = num;
}

Can become:

for(i = 0; i < n; i++) 
{
    scanf("%d", &num);
    set1[1][i] = 0;
    set1[0][i] = num;
}

Answer 3

Amusingly enough I'm working right this moment on optimizing this exact kind of problem in a real production system and I needed to rest my brain so I clicked here.

As Gareth pointed out in his answer, your algorithm is just too inefficient to do this in time.

With the time limits you have and just two arrays there's a relatively simple algorithm that should be fast enough for you:

1. Sort both input arrays (with something better than what you have implemented in there, your sort is another reason why your code is too slow).
2. keep track of an index into each array you need to intersect, start indexes at 0.
3. compare the elements at their respective index. If equal, output one result and increment both indexes, if not equal, increment the index of the input array with the lower element.
4. continue until you reach the end of both arrays.

That is the simplest algorithm to do this and in your case it should be fast enough. But if it isn't, we can do always do better.

1. Sort both input arrays.
2. Keep track of an index into each array, start at 0.
3. Compare elements at their respective index. If equal output one result and increment both indexes. goto 3.
4. Since the elements were not equal, pick the greater of the two elements, binary search in the other array for an element greater than or equal to that element. Set the index of the lower array to the result of the binary search. goto 3.
5. Continue until you reach the end of both arrays (or the binary search returns no result).

Still not fast enough? For certain types of data where the numbers aren't too sparse and the input sets are big enough you can build bitmaps for each of the input sets and intersect them in one go with bitwise and.