Solution


  • 0
    S

    Approach 1# :- By sorting of array
    Complexity: O(n log n ) where m and n is the length of respective arrays.
    Space Complexity; O(x) where x is the number of elements in intersection array.

    Steps:- 1. First sort the input array by using the comparator function, as the input numbers in the arrays are in string format . below is the comparator function
    function comp(a,b)
    {
    return a-b;
    }
    using this comp function sort function of the array will sort the array.
    Now we can track which element is matching by comparison of numbers.

    1. For comparison of two array elements we will track the index of the compared element by x and y;
      if ums1[x] is less than ums2[y] then we will increase x by one so that next larger element of ums1 can be compared with that of ums2; same for if nums2[y] less than nums1[x] then will increase y by one;
      in case any of the value x or y reaches to the max index we will store the iteration.
      below is the working code example in JavaScript
    var intersect = function(nums1, nums2) {
        var comp=function(a,b){
           return a-b
       }
        nums1.sort(comp);
        nums2.sort(comp);
        var arr=[];
        var x=0,y=0;
        while(x<nums1.length && y<nums2.length){
            let _x=nums1[x];
            let _y=nums2[y];
            if(_x==_y){
                arr.push(_x);
                x++;
                y++;
            }
            else if(_x>_y){ y++;}
            else{ x++;}
        }
        return arr;
    };
    

    Approach 2:
    Complexity: O(n+m)
    Space Complexity: O(n)
    In the approach we can use object which will store numbers as key and its count as value.
    and later use that count to find out the common numbers in array. code example below.

    var intersect = function(nums1, nums2) {
        var obj={};
        var arr=[];
        for(let i of nums1){
            let x=obj[i];
            if(x){
                obj[i]=x+1;
            }
            else{
                obj[i]=1;
            }
        }
         for(let i of nums2){
            let x=obj[i];
            if(x){
                arr.push(i);
                obj[i]=x-1;
            }   
        }  
        return arr;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.