Problem overview
The method intersection receives two arrays of integers, first and second. It returns the numbers that appear in both, each exactly once, sorted from smallest to largest.
For first = [1, 2, 2, 1] and second = [2, 2] the answer is [2]: only 2 is shared, and it appears once in the result however often it repeats. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4] the answer is [4, 9]. Both 4 and 9 are in both arrays, and the 5 and the 8 each belong to one array only.
The lesson asks for O(n + m) time, plus the sort of the shared numbers, where n and m are the lengths of the two arrays.
Approach: a set answers "is it in the other array?"
The direct way is to take each number of first and scan second for it. That is O(n × m), because each question "is this number in the other array?" costs a whole scan.
A Set answers that question in constant time on average. Put every number of second into a set once. Then walk through first and, for each number, ask the set. Only numbers present in both arrays pass the test.
That leaves the duplicates. If the number 2 appears twice in first, it must be added to the answer only once. The trick is to delete a number from the set the moment it is added to the answer. Its repeats then fail the test, because the set no longer contains it. Adding repeated values to a set changes nothing, so duplicates in second need no care at all.
Finally, the numbers come out in the order of first, not in numeric order, so a sort finishes the job. On first = [4, 9, 5] the matching numbers are found in the order 4, 9, which happens to be sorted, but first = [9, 4] would give [9, 4] before sorting.
Step by step
- Give the inputs shorter names:
nums1andnums2. This copies nothing; both names point to the same arrays asfirstandsecond. - Create the empty answer array
ans, typednumber[]. The shared numbers will be pushed onto it. - Create an empty
Set<number>namedset. It will hold the numbers ofnums2. - Write a loop over the indexes of
nums2. The whole ofnums2must be in the set beforenums1is examined. - Add
nums2[i]to the set. A number that is already there is ignored, so repeats take care of themselves. - Write a second loop over the indexes of
nums1, usingj. - Test
set.has(nums1[j]). It is true only for numbers that occur innums2. - Push
nums1[j]ontoansinside theif: this number is in both arrays. - Delete
nums1[j]from the set right after. Later copies of the same number innums1now fail the test, so each shared number is added once. - Sort
ansand return it, withans.sort((a, b) => a - b).
The solution in TypeScript
class Solution {
intersection(first: number[], second: number[]): number[] {
let nums1 = first, nums2 = second;
let ans: number[] = [];
let set = new Set<number>();
for (let i = 0; i < nums2.length; i++) {
set.add(nums2[i]);
}
for (let j = 0; j < nums1.length; j++) {
if (set.has(nums1[j])) {
ans.push(nums1[j]);
set.delete(nums1[j]);
}
}
ans.sort((a, b) => a - b);
return ans;
}
}
The TypeScript details worth a closer look:
Set<number>. ASetstores unique values. The type argument is erased at run time, and it only helps the compiler check what you add.add,hasanddeletetake constant time on average.- The comparator is required. Without one,
sort()compares elements as strings, so[10, 9, 1, -5].sort()gives[-5, 1, 10, 9]. With(a, b) => a - b, a negative result putsafirst, giving numeric order:[10, 9, 1, -5]becomes[-5, 1, 9, 10]. Constraints allow negative numbers and numbers with different digit counts, so both cases matter. sortworks in place. It reordersansand returns the same array, which is why the next line can returnans.- Aliasing, not copying.
let nums1 = firstmakes a second name for the same array. That is fine here because neither array is modified. letversusconst. Nothing here is reassigned, soconstwould be the more idiomatic choice. The lesson's code works the same withlet.
Complexity
Let n and m be the lengths of first and second, and r the number of shared values.
Time: O(n + m + r log r). Filling the set takes m constant-time additions, the second loop takes n constant-time checks, and the final sort handles only the r shared values. Since r is never larger than the smaller array, this is within the lesson's O(n + m) plus the sort.
Space: O(m + r). The set holds up to m distinct numbers and the answer holds r.
Edge cases and common mistakes
- No shared numbers.
first = [1, 2]withsecond = [3]gives an empty array,[]. - Repeats in
first. In the first example, the 2 matches once, is deleted from the set, and is skipped on its repeat. Without the delete the answer would be[2, 2]. - Repeats in
second. They make no difference, because adding a present value to a set does nothing. - Forgetting the comparator.
[10, 9]would stay as[10, 9]with default sorting, because the text"10"sorts before"9". - Negative numbers. A set treats
-5like any other number. The comparator also puts negatives first, sofirst = [10, 9, -5]andsecond = [9, 10, -5]give[-5, 9, 10]. - Using
includeson the array.nums2.includes(x)works, but scans the array each time and brings back theO(n × m)cost.
Testing
first = [1, 2, 2, 1],second = [2, 2]gives[2].first = [4, 9, 5],second = [9, 4, 9, 8, 4]gives[4, 9].first = [1, 2],second = [3]gives[].first = [10, 9, -5],second = [9, 10, -5]gives[-5, 9, 10].
