Integer Array Intersection

Let’s think about 2 integer arrays.

int[] nums1 = {1, 2, 3, 9, 9, 9, 8, 5};
int[] nums2 = {9, 9};

Need to write a function that returns the common elements in both arrays. In this example, nums2 has two 9’s and nums1 has three 9’s, so the function must return {9, 9} (two 9’s).

I’ve solved the problem but I’m not sure if I have done it in the most efficient way. I will show my code below.

    public void testIntersect()
    {
        Integer[] nums1 = {9, 6, 8, 9, 9};
        Integer[] nums2 = {9, 8, 9, 5, 5, 5, 5};

        int[] result = intersect(nums1, nums2);
        for (int i : result)
        {
            System.out.println(i);
        }
    }

    public int[] intersect(Integer[] nums1, Integer[] nums2) {
        List<Integer> longer;
        Integer[] shorter;
        if (nums1.length < nums2.length) {
            longer = Arrays.stream(nums2).collect(Collectors.toList());
            shorter = nums1;
        }
        else {
            longer = Arrays.stream(nums1).collect(Collectors.toList());
            shorter = nums2;
        }

        List<Integer> result = new ArrayList<>();

        for(int i = 0; i < shorter.length; i++) {
            if (longer.contains(shorter[i])) {
                longer.remove(shorter[i]);
                result.add(shorter[i]);
            }
        }
        return result.stream().mapToInt(i -> i).toArray();
    }

The first thing I thought of doing is that I want to iterate through the shorter array so I declared longer as List<Integer> and shorter as just an integer array. The reason the longer variable is declared as List<Integer> is because I need to be able to remove elements from it. The logic is that if an element in the shorter array, the element in the longer array should be removed because if shorter contains two 9’s and longer array contains a single 9, the second 9 in the shorter array should not match the 9 in the longer array.

result variable as List<Integer> contains the matched elements and it finally returns the array.

The time complexity for this code may be O(n) and the space complexity may be O(2n).

I’m thinking there may be cleverer ways to accomplish this…

Author: admin

A software engineer in greater Seattle area

Leave a Reply

Your email address will not be published. Required fields are marked *