Leetcode 349) Intersection of Two Arrays

19 Sep 2021 in Algorithms

My solution

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //to make it nlog(n)
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int l1=0;
        int l2=0;

        int r1=nums1.length;
        int r2 = nums2.length;

        Set<Integer> res=new HashSet<>();
        while(l1!=r1 && l2!=r2){
            if(nums1[l1] == nums2[l2]){
                res.add(nums1[l1]);
                l1++;l2++;
            }else if (nums1[l1] <nums2[l2]){
                l1++;
            }else if(nums1[l1]>nums2[l2]){
                l2++;
            }
        }

        if(l1==r1){
            //nums2 has lots of elements left.
            while(l2!=r2){
                if(nums1[r1-1]==nums2[l2]){
                    res.add(nums2[l2]);
                    break;
                }else{
                    l2++;
                }
            }
        }else{
            while(l1!=r1){
                if(nums2[r2-1]==nums1[l1]){
                    res.add(nums1[l1]);
                    break;
                }else{
                    l1++;
                }
            }
        }
        int[] ary= new int[res.size()]; 
        int cnt =0;
        for(int i : res){
            ary[cnt++]=i;
        }
        return ary;
    }
}

Other Answer

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        int[] res = new int[1001];
        if(nums1.length < nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        
        for(int x : nums1) res[x]++;
        for(int x: nums2) if(res[x] > 0) set.add(x);
        
        int index = 0;
        for(int x : set) res[index++] = x;
        
        return Arrays.copyOfRange(res, 0, index);
    }
}

Set

• put nums1 array to set, and iterate nums2 array . Add overlapped elements in another set and return as array.

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> s = new HashSet<>();
        Set<Integer> intersection = new HashSet<>();

        for(int i=0;i<nums1.length;i++){
            s.add(nums1[i]);
        }

        for(int i=0;i<nums2.length;i++){
            if(s.contains(nums2[i])){
                intersection.add(nums2[i]);
            }
        }

        int[] res = new int[intersection.size()];
        int ind =0;
        for(int i:intersection ){
            res[ind]=i;
            ind++;
        }
        return res;
    }

}