Problem overview
intersection(first, second) takes two IntArray values and returns an IntArray of the numbers that appear in both. Each shared number is listed once, however often it occurs, and the result is sorted in ascending order.
For first = [1, 2, 2, 1] and second = [2, 2] the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4] the answer is [4, 9]: both numbers are in both arrays, and although each appears twice in second, the result holds it once. If nothing is shared, the result is an empty array. Each array has between 1 and 1000 elements, and each value is between -1000 and 1000.
The lesson asks for O(n + m) time, plus the time to sort the shared numbers, where n and m are the array sizes.
Approach: remember one array in a set
The obvious solution checks every element of first against every element of second, which takes O(n × m). The question being asked each time is simply "does this number occur in the other array?", and a hash set answers that in constant time on average.
So the plan has three parts:
- Put every number of
firstinto a set calledseen. A set stores each value once, so repeats vanish by themselves. - Go through
second. Each number that is inseenbelongs to both arrays, so add it to a second set,intersectionSet. That set also drops repeats, so a number that shows up twice insecondis still stored once. - A hash set has no useful order, but the answer must be ascending. Sort the shared numbers at the end and copy them into an
IntArray.
With first = [4, 9, 5] and second = [9, 4, 9, 8, 4], seen becomes {4, 9, 5}. Walking through second: 9 is in seen, so it is added; 4 is added; the next 9 is already in the result set, so nothing changes; 8 is not in seen; the last 4 changes nothing. The shared set is {9, 4}, and sorting gives [4, 9].
Only the sort costs more than linear time. If k numbers are shared, it adds O(k log k), which is why the lesson's budget says "plus the time to sort the shared numbers".
Step by step
- Give the inputs shorter names.
nums1andnums2arevalaliases offirstandsecond. No array is copied: both names refer to the same array. - Create the first set. A
HashSet<Int>namedseenwill hold the numbers ofnums1. - Loop over
nums1. Every number must be inseenbeforenums2is examined. - Add each number. Adding a value that is already present changes nothing.
- Create the result set. A second
HashSet<Int>,intersectionSet, collects the shared numbers. - Loop over
nums2. Each of its numbers is tested in turn. - Test membership. If
seen.contains(i), the number is in both arrays, so add it tointersectionSet. - Return it sorted.
sorted()puts the numbers in ascending order, andtoIntArray()converts the result to theIntArraythe function must return.
The solution in Kotlin
class Solution {
fun intersection(first: IntArray, second: IntArray): IntArray {
val nums1 = first
val nums2 = second
val seen = HashSet<Int>()
for (i in nums1) {
seen.add(i)
}
val intersectionSet = HashSet<Int>()
for (i in nums2) {
if (seen.contains(i)) {
intersectionSet.add(i)
}
}
return intersectionSet.sorted().toIntArray()
}
}
Kotlin details worth a look:
IntArray, sets and boxing. AnIntArrayholds primitive ints, while aHashSet<Int>stores boxedIntegerobjects. Kotlin converts between them automatically in the loops, andtoIntArray()converts the sorted list back.sorted()returns a newList<Int>. It doesn't change the set, which couldn't be reordered anyway.toIntArray()then builds an array from that list.addreturns aBoolean:trueif the value was new andfalseif the set already held it. The solution ignores that result, which is fine.- Printing an array.
println(result)on anIntArraydoesn't show the numbers. It prints a type tag and a hash code, in the form[I@followed by hexadecimal digits. To see the contents, useresult.contentToString(), which gives[4, 9]. for (i in nums1)loops over the elements directly, with no index.
Complexity
Time: O(n + m) plus O(k log k). Building seen takes n additions and scanning second takes m lookups, each constant time on average. Sorting the k shared numbers adds k log k, where k is at most the smaller array's size.
Space: O(n + k). seen holds up to n distinct values, and intersectionSet, the sorted list and the result array each hold at most k values.
Edge cases and common mistakes
- No shared numbers.
[1, 2]and[3, 4]give an empty array, printed as[]. - Repeated numbers. The result must not contain duplicates. Collecting matches in a list instead of
intersectionSetwould return[2, 2]for the first example. - Negative values. Sorting handles them:
[-1, -3, 5]and[5, -3, -1]give[-3, -1, 5]. - Skipping the sort. A
HashSetdoesn't promise any order, so the result must be sorted explicitly, or the output may not match the expected ascending order. - Checking against the wrong array. The set must hold one array completely before the other is scanned. Checking while still filling it misses numbers that appear later in
first.
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, 4]gives[].first = [-1, -3, 5],second = [5, -3, -1]gives[-3, -1, 5].
