Several Java solutions with explanation


  • 2
    O

    Solution using Java Collections

    1. Convert first array to the set

    2. Convert second array to the set

    3. Use retainAll to find set intersection

    4. Convert intersection set to array

      // O(max(n, m)) time, O(n + m) space
      public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> a = new HashSet<>(Arrays.stream(nums1).boxed().collect(Collectors.toList()));
        Set<Integer> b = new HashSet<>(Arrays.stream(nums2).boxed().collect(Collectors.toList()));
        a.retainAll(b);
        return a.stream().mapToInt(Integer::intValue).toArray();
      }
      

    Solution sing sorting

    1. Sort first array

    2. Sort second array

    3. Use two pointers to traverse first and second sorted arrays

    4. If first pointer points to bigger value - move the second pointer

    5. If second pointer points to bigger value - move the first pointer

    6. If pointers point to equal values add it to result array and move both pointers to the next distinct value

    7. Repeate 4-6 until any pointer reaches the end of array

    8. Shrink the size of intersection array to remove unused space

      // O(max(n, m) log max(n, m)) time, O(min(n, m)) space
      public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] intersect = new int[Math.min(nums1.length, nums2.length)];
        int i = 0;
        for (int p1 = 0, p2 = 0; p1 < nums1.length && p2 < nums2.length;) {
          while (p1 < nums1.length && nums1[p1] < nums2[p2]) {
            p1++;
          }
          while (p1 < nums1.length && p2 < nums2.length && nums1[p1] > nums2[p2]) {
            p2++;
          }
          if (p1 < nums1.length && p2 < nums2.length && nums1[p1] == nums2[p2]) {
            intersect[i++] = nums1[p1];
            while (p1 < nums1.length && nums1[p1] == intersect[i-1]) {
                p1++;
            }
            while (p2 < nums2.length && nums2[p2] == intersect[i-1]) {
                p2++;
            }
          }
        }                
        int[] result = new int[i];
        for (; i-1 >= 0; i--) {
          result[i-1] = intersect[i-1];
        }
        return result;
      }
      

    Brute-force solution

    1. For each element in first array traverse second array

    2. While traversing second array check for values match

    3. If there is a match check if it is unique by traversing intersection array

    4. If match is unique add it to intersection array.

    5. Shrink intersection array

      // nums1.length = n, nums2.length = m
      // O (n * m * min(n, m)) time, O(min(n, m)) space
      public int[] intersection(int[] nums1, int[] nums2) {
        int[] intersect = new int[Math.min(nums1.length, nums2.length)];
        int index = 0;
        for (int i = 0; i < nums1.length; i++) {
          for (int j = 0; j < nums2.length; j++) {
            if (nums1[i] == nums2[j]) {
              boolean isUnique = true;
              for (int k = 0; k < index; k++) {
                if (nums1[i] == intersect[k]) {
                  isUnique = false;
                }
              }
              if (isUnique) {
                intersect[index++] = nums1[i];   
              }
            }
          }
        }
        int[] result = new int[index];
        for (; index-1 >= 0; index--) {
          result[index-1] = intersect[index-1];
        }
        return result;
      }

Log in to reply
 

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