DSA problem
Intersection of Two Arrays
Given two arrays, find their intersection - the elements that appear in both. Each element in the result should appear as many times as it shows in both arrays.
The hash map approach is optimal: build a frequency map from the first array, then iterate through the second array. For each element, if it exists in the map with count greater than 0, add it to the result and decrement the count. This handles duplicates correctly in O(M + N) time.
An alternative for sorted arrays uses two pointers, advancing the smaller side and recording equal elements. This is a building block for merging intervals, finding common elements across arrays, and database joins.
Examples
nums1 = [1, 2, 2, 1], nums2 = [2, 2][2, 2]Constraints
- 1 <= nums1.length, nums2.length <= 10^5
- -10^9 <= nums1[i], nums2[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.