Right after I wrote the previous blog entry regarding integer array intersection, I thought of sorting the two parameters before I did anything with those arrays. I think I came up with a better algorithm. Let’s look at the code.

```
public void testIntersect2()
{
int[] nums1 = {4,7,9,7,6,7};
int[] nums2 = {5,0,0,6,1,6,2,2,4};
int[] result = intersect2(nums1, nums2);
for (int i : result)
{
System.out.println(i);
}
}
private int[] intersect2(int[] nums1, int[] nums2)
{
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] shorter;
int[] longer;
if (nums1.length < nums2.length) {
shorter = nums1;
longer = nums2;
}
else {
shorter = nums2;
longer = nums1;
}
int[] nums = new int[shorter.length];
int j = 0;
int index = 0;
for(int i = 0; i < shorter.length; i++) {
while (j < longer.length && shorter[i] >= longer[j]) {
if (shorter[i] == longer[j]) {
nums[index] = shorter[i];
index++;
j++;
break;
}
j++;
}
}
int[] result = new int[index];
for(int i = 0; i < index; i++)
{
result[i] = nums[i];
}
return result;
}
```

What’s better about the second attempt on this algorithm is I did not create an ArrayList for `longer`

variable. It takes less space. The only extra data in the memory is the `result`

as `int[]`

so space complexity-wise it’s O(n+1) = O(n). Also convering ArrayList<Integer> to int[] seems to take some time. When I measured the code execution time, my previous code took 34 ms but this one took only 1 ms. It doesn’t seem much because it’s only 34 ms with the less efficient code but if the system execute the function millions and billions of times, it adds up!

So the logic is that you iterate through the sorted `shorter`

integer array from the first element and you move each element in the `longer`

one until the element matches the one in the `longer`

array or the value in the `shorter`

array is greater than equal to the current element in the `longer`

array.

With this algorithm, we are iterating the shorter variable once and the longer one just about once (or less). The time complexity may be O(n).

After all, sorting the integer array at the beginning was a good idea. ðŸ™‚