Question
|
Difficulty Level:
1
|
Solution
|
Explanation Quality:4
|
This question basicaly aims to test if you are able to solve the problem in linear
time. The brute force solution would be to compare each element of a given array
to all the elements of the other array to find the intersection which would take
O(n2) time. However we will try to do the problem in linear time.
The startegy is that we take note of the word 'sorted' in the problem. If the arrays
are sorted we must take advantage of this fact. So we pick one array and pick it's
first element. Next we compare it to the first element of the second array. If they
are the same we print an intersection. If the first array's element is less than
we increment the pointer in our first array because we know that a higher value
might be lying in the first array which can match the first element of the second
array. However if the first array's first element is greater than the second array's
first element then we increment the pointer in the second array since we might find
a higher value element in the second array which might be the same as that of the
first element of the first array.
Note that we always increment the array pointer which is pointing to the lesser
value element of the two pointers. This is because we already know that the elements,
ahead of the higher value element being pointed by one of the pointers, are greater
in value and thus a match is impossible. However, on the contrary the array which
currently has a lower value element has the possibility of having a higher value
element in forward slots which might give a match.
Lastly, we also need to detect when we reach the end of the two arrays. Here's the
code:
int i,j; //i points to array1 and
j points to array2
for(i=0;i<length_of_array1;/*don't increment i here*/){
if(j == length_of_array2)
break; //scanned all of array2
if(array1[i] == array[j]){
print intersection
i++;
j++;
continue;
}
if(array[i] < array[j]){
i++; //array1 has smaller element so increment it
continue;
}
if(array[i] array[j]){
j++; //array2 has smaller element so increment it
continue;
}
|