Question

LeetCode Link | 349. Intersection of Two Arrays | Easy

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.

Constrains

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

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 Approach

Method: Unordered Set / Hash Table

Constrains

  • Element in the result is unique
  • Result does not require order

This question can also to be solved using array since it constrains the number from 0 to 1000. If this question not limit the value, this will not work anymore. And If the hash values are few, particularly dispersed, and span a very large range, using an array would result in a significant waste of space.

Concept Explanation

This question are designed to use unordered set based on its constrains. The underlying of the unordered set is implement by hash table, and it has the highest read and write efficiency.

We need two sets to get the result. It use one set to remove duplicate elements in nums1, and use another sets to check if element in nums2 exits in that set generated from nums1, then add this element into the second set, and return this set as a array at the end.

The use of unordered set

Code

  • m is the time that convert set to array
  • Time complexity: O(n + m)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
// Normal way
function intersection(nums1: number[], nums2: number[]): number[] {
    let resultSet: Set<number> = new Set();
    let num1Set: Set<number> = new Set(nums1);
    for (let i = 0; i < nums2.length; i++) {
        if (num1Set.has(nums2[i])) resultSet.add(nums2[i]);
    }
    return Array.from(resultSet);
};
1
2
3
4
// Fancy way
function intersection(nums1: number[], nums2: number[]): number[] {
  return Array.from(new Set(nums1.filter(i => nums2.includes(i))));
}

Conclusion

When there is a question need you to iterate without sorting and require unique data, using unordered_set is always your first choice. However, if there is a constrains for data range, use array first. Using a set not only occupies more space than an array, but it is also slower because the set has to perform hash calculations to map values to keys. Do not underestimate the time consumption; with large amounts of data, the difference is significant!