Problem

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Examples

Example 1:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]  
Output: [2]

Example 2:

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]  
Output: [9,4]  
Explanation: [4, 9] is also accepted.

Solution

Method 1 - Using 2 HashSets

Here are the steps to follow:

  1. Store all unique elements of nums1 in set1.
  2. For each element in nums2, if it exists in set1, add it to set2.
  3. Convert set2 to an integer array ans.
  4. Return the array ans containing the intersection of nums1 and nums2.

Here is the detailed video explanation:

Code

Java
class Solution {

	public int[] intersection(int[] nums1, int[] nums2) {
		HashSet<Integer> set1 = new HashSet<Integer>();

		for (int num: nums1) {
			set1.add(num);
		}

		HashSet<Integer> set2 = new HashSet<Integer>();

		for (int num: nums2) {
			if (set1.contains(num)) {
				set2.add(num);
			}
		}

		int[] ans = new int[set2.size()];
		int i = 0;

		for (int num: set2) {
			ans[i++] = num;
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(m + n) where m and n is size of of nums1 and nums2.
  • 🧺 Space complexity: O(m + n)

Method 2 - Using 1 HashSet

Code

Java
class Solution {

	public int[] intersection(int[] nums1, int[] nums2) {
		HashSet<Integer> set1 = new HashSet<Integer>();

		for (int num: nums1) {
			set1.add(num);
		}
		List <Integer> intersection = new ArrayList<Integer>();
		for (int num: nums2) {
			if (set1.contains(num)) {
				intersection.add(num);
				set1.remove(num);
			}
		}

		int[] ans = new int[intersection.size()];
		int i = 0;

		for (int num: intersection) {
			ans[i++] = num;
		}

		return ans;
	}
}

Method 3 - Binary Search

Here are the steps we can follow:

  1. Sort the arrays.
  2. Create a list to store the intersection results.
  3. Find unique elements in nums1 and check for their presence in nums2 using binary search.
  4. Convert the intersection list to an ans array.
  5. Return the ans array containing the intersection of nums1 and nums2.

Code

Java
class Solution {

	public int[] intersection(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);

		ArrayList<Integer> ansList = new ArrayList<Integer>();

		for (int i = 0; i < nums1.length; i++) {
			if (i == 0 || (i > 0 && nums1[i] != nums1[i - 1])) {
				if (Arrays.binarySearch(nums2, nums1[i]) > -1) {
					ansList.add(nums1[i]);
				}
			}
		}

		int[] ans = new int[ansList.size()];

		// Convert ArrayList to int array (and can't be used as a variable name)
		int k = 0;

		for (int num: ansList) {
			ans[k++] = num;
		}

		return ans;
	}

}

Complexity

  • ⏰ Time complexity: O(m log m + n log n) where m and n is size of of nums1 and nums2. Mainly, for sorting two arrays and O(n log m) for searching elements elements in nums1 in nums2.
  • 🧺 Space complexity: O(n) for using ansList