Integer Array Intersection (Improved)

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. 🙂