Leetcode 350 - Intersection of Two Arrays II [2/7/24]

Time Taken: ~5 mins
Tag: LeetCode Easy
Concept: Counting Sort
High-level ideas:
- Since range of value of nums is from 0 to 1000 inclusive only, we can use counting sort.
- Keep track of 2 arrays (“freq1”, “freq2”) of length 1001 for “nums1” and “nums2” respectively and store information of the frequency of occurrence of index.
- e.g. freq1[0] contains frequency of occurrence of 0 in “nums1”.
- e.g. freq2[5] contains frequency of occurrence of 5 in “nums2”.
- Afterwards, iterate through the “freq1” and “freq2” simulataneously. Overlapping frequency of an index would be the minimum frequency of the 2 values
- e.g. freq1[3] = 10, freq2[3] = 5. This means the overlap between “nums1” and “nums2” for number 3 is “min(5,10) = 5 times”.