My Submissions

Given two arrays, write a function to compute their intersection. **Example:**Given nums1 = [1, 2, 2, 1] , nums2 = [2, 2] , return [2] . Note: Each element in the result must be unique. The result can be in any order.

Hide Company Tags  Two Sigma Hide Tags  Binary Search Hash Table Two Pointers Sort Hide Similar Problems  (E) Intersection of Two Arrays II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class Solution {
    // https://discuss.leetcode.com/topic/45685/three-java-solutions
    
    // Time O(nlogn)  two pointers
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0, j = 0;
        while ( i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        int[] result = new int[set.size()];
        int k = 0;
        for(Integer num : set) {
            result[k++] = num;
        }
        return result;
    }
    
    
    //Time O(n) Space O(n)
    public int[] intersection1(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> intersect = new HashSet<>();
        
        for(int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);  
        }
        
        for (int j = 0; j < nums2.length; j++) {
            if (set.contains(nums2[j])) {
                intersect.add(nums2[j]);
            }
        }
        
        int[] result = new int[intersect.size()];
        int i = 0;
        for (int num : intersect) {
            result[i++] = num;
        }
        
        return result;
    }
}