Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Follow up:
nums1's size is small compared to nums2's size? Which algorithm is better?nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?This approach involves using a hash map (or dictionary) to keep track of the frequencies of elements in one of the arrays, then iterating through the second array to identify common elements, decrementing the frequency count accordingly.
We use Python's collections.Counter to track element frequencies in nums1. Then, we iterate through nums2, checking if the current element exists in the counter with a non-zero count: if so, we add the element to the intersection result and decrease its count in the counter.
JavaScript
Java
C++
C
C#
Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(min(n, m)) due to the counter.
Another efficient way is to first sort both arrays and then use two pointers to identify intersections. This approach harnesses the ordered nature post-sort to efficiently match elements by moving through both arrays simultaneously.
Both arrays are initially sorted, and two pointers i and j iterate from the start of nums1 and nums2 respectively, by comparing elements. If matching, we add to the result; else, movements depend on comparatives.
JavaScript
Java
C++
C
C#
Time Complexity: O(n log n + m log m) due to sorting of nums1 and nums2. Space Complexity: O(1) extra space is used, aside from the outputs.
| Approach | Complexity |
|---|---|
| Using Hash Maps for Frequency Count | Time Complexity: O(n + m), where n and m are the lengths of |
| Using Sorting and Two Pointers | Time Complexity: O(n log n + m log m) due to sorting of |
Intersection of Two Arrays II Leetcode daily challenge || Intuition + Code + Explanation • Code with Alisha • 38,852 views views
Watch 9 more video solutions →Practice Intersection of Two Arrays II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor