5ms Java Using 1 hashset and time complexity of O(m+n)


  • 24
    M
    HashSet<Integer> set = new HashSet<Integer>();
            ArrayList<Integer> res = new ArrayList<Integer>();
            //Add all elements to set from array 1
            for(int i =0; i< nums1.length; i++) set.add(nums1[i]);
            for(int j = 0; j < nums2.length; j++) {
               // If present in array 2 then add to res and remove from set 
               if(set.contains(nums2[j])) {
                    res.add(nums2[j]);
                    set.remove(nums2[j]);
                }
            }
            // Convert ArrayList to array
            int[] arr = new int[res.size()];
            for (int i= 0; i < res.size(); i++) arr[i] = res.get(i);
            return arr;

  • 0
    K

    ok, but are you sure contains method is constant complexity ?


  • 0
    M

    Yes, set works similar to how map works, so it will hash the value and search in that particular index.
    http://stackoverflow.com/questions/25247854/hashset-contains-performance


  • 0
    K

    @mitulshr oh yes that is right, I forgot it uses hash function .


  • 0
    V

    Why did you remove the element?


  • 1
    Y

    We use remove function to avoid calculating twice when same numbers contained in the second array. For example, nums1 = [2,2], nums2 = [1,2,2,1]. Without remove function, "2" in nums2 will be counted twice. Since we only need one "2", we need set.remove().


  • 0
    C

    OMG I considered this problem more complicated because I think we need to consider the count of each arrays. I mean if nums1 has two '2', the nums2 must have exactly two '2' for intersection. So I used HashMap to store element and count by Key and values.


  • 1
    H

    Same idea, but shorter code,

        class Solution {
            public int[] intersection(int[] nums1, int[] nums2) {
                Set<Integer> numbers = new HashSet<>();
                for (int n : nums1) { numbers.add(n); }
                int[] res = new int[numbers.size()];
                int cursor = 0;
                for (int n : nums2) {
                    if (numbers.remove(n)) {
                        res[cursor++] = n;
                    }
                }
                return Arrays.copyOfRange(res,0,cursor);
            }
        }
    

Log in to reply
 

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