singularity

singularity 🔎

350. Intersection of Two Arrays II

Naive O(n^2)

var intersect = function (nums1, nums2) {
    let i = []
    let s = Math.min(nums1.length, nums2.length) == nums1.length ? nums1 : nums2
    let b = s == nums1 ? nums2 : nums1
    let sl = s.length - 1

    while (sl >= 0) {
        let e = s[sl]
        let ib = b.indexOf(e)
        if (ib != -1) {
            i.push(e)
            b.splice(ib, 1)
        }
        sl--
    }

    return i
};

O(n+m) with hashmap

function intersect(nums1, nums2) {
    const counts = {};
    const result = [];

    nums1.forEach(el => counts[el] = ++counts[el] || 1);

    for (let el of nums2) {
        if (counts[el]) {
            result.push(el);
            counts[el]--;
        }
    }

    return result;
};

O(n log n) with [binary search]

var intersect = function(nums1, nums2) {
    nums1.sort((a,b)=>a-b); nums2.sort((a,b)=>a-b);
    let output=[];
    for(let i=0; i<nums1.length; i++){
        if(binary(nums1[i])){
			output.push(nums1[i]);
		}
    }
    return output;
    
    function binary(n){
        let l=0, r=nums2.length-1;
        while(l<r){
            let mid=l+Math.floor((r-l)/2);
            if(nums2[mid]<n){
				l=mid+1;
			}else{
				r=mid;
			}
        }
        if(nums2[l]==n){
            nums2[l]=-Infinity; return true;
        }
        return false;
    }
};