Problem overview
The method intersection(first: Array[Int], second: Array[Int]): Array[Int] returns the numbers that appear in both arrays. Each number is listed once, however often it occurs, and the result is sorted in ascending order. Each array has between 1 and 1000 elements, with values from -1000 to 1000.
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 the repeats in second add nothing.
The lesson asks for O(n + m) time, plus the time to sort the shared numbers, where n and m are the lengths of the arrays.
Approach: remember one array in a set
The simple way to find shared numbers is to take each number of first and scan second for it. That costs O(n × m). The question being asked over and over is "does this number occur in that array?", and a hash set answers it in O(1) on average.
So the plan has two passes:
- Put every number of
firstinto a set calledseen. A set stores each value once, so repeats vanish. - Walk through
second. For each number that is inseen, add it to a second set,intersectionSet.
A number reaches intersectionSet only if it was in first (it is in seen) and in second (the loop is looking at it). Since this is also a set, a shared number that appears many times in second is stored once, which is what the problem wants.
The last step is the order. A hash set has no useful order, so the shared numbers are copied into an array and sorted. With first = [4, 9, 5] and second = [9, 4, 9, 8, 4]: seen becomes {4, 9, 5}, the second pass finds 9, 4, 9 and 4 in it, and intersectionSet is {9, 4}. Sorting gives [4, 9].
The two passes cost O(n) and O(m). Sorting k shared numbers costs O(k log k), which is the "plus the time to sort" in the lesson's note.
Step by step
- Give the inputs shorter names.
nums1andnums2are just aliases forfirstandsecond. No numbers are copied. - Create the first set.
seenis an emptyscala.collection.mutable.Set[Int]. It will hold the numbers ofnums1. - Loop over
nums1. Every number of the first array must be inseenbefore the second array is checked. - Add each number.
seen += iinserts it. Adding a number that is already there changes nothing. - Create the result set.
intersectionSetis a second empty mutable set. It will hold the shared numbers once each. - Loop over
nums2. Each number is tested againstseen, one at a time. - Keep the shared ones. If
seen.contains(i), additointersectionSet. - Return a sorted array.
toArraycopies the set into anArray[Int], andsortedputs it in ascending order.
The solution in Scala
class Solution {
def intersection(first: Array[Int], second: Array[Int]): Array[Int] = {
val nums1 = first
val nums2 = second
var seen = scala.collection.mutable.Set[Int]()
for (i <- nums1) {
seen += i
}
var intersectionSet = scala.collection.mutable.Set[Int]()
for (i <- nums2) {
if (seen.contains(i)) {
intersectionSet += i
}
}
return intersectionSet.toArray.sorted
}
}
The Scala details worth a closer look:
- Mutable versus immutable sets. A plain
Setin Scala is immutable, and+=on avarholding one would build a new set each time and reassign the variable. The code usesscala.collection.mutable.Set, which changes in place. Because the sets are mutable, thevardeclarations are not strictly needed: avalwould work equally well, since only the contents change. +=on a mutable set.seen += iadds the element to the same set object. Adding an existing element is allowed and does nothing.contains.seen.contains(i)returns aBooleanand isO(1)on average for a hash set. The shorter formseen(i)means the same.toArray.sorted.toArrayon amutable.Set[Int]gives anArray[Int], andsortedreturns a new sorted array, using the natural order ofInt. The set's own order is unspecified, so never rely on it.- Looping over an array.
for (i <- nums1)visits each element in order, withianInt. The namesihere are values, not indices. - The last expression.
return intersectionSet.toArray.sortedis outside of any loop, so the explicitreturnis an ordinary one.
Complexity
Time: O(n + m) plus the sort. The first loop does n insertions and the second does m lookups and at most m insertions, each O(1) on average. Sorting the k shared numbers adds O(k log k), where k can't exceed the smaller of the two lengths.
Space: O(n + k). seen holds up to n numbers, the result set holds up to k, and the returned array has k elements. With values limited to -1000 to 1000, each set has at most 2001 entries.
Edge cases and common mistakes
- No shared numbers.
[1, 2]and[3, 4]give an empty array,[]. The loops run normally and the result set stays empty. - Repeats.
[1, 2, 2, 1]and[2, 2]give[2], not[2, 2]. Using a list or an array for the result instead of a set would keep the duplicates. - Negative numbers.
[-1, 0, 5]and[5, -1, -1]give[-1, 5]. Sorting orders them numerically, so the negative one comes first. - Forgetting to sort. The order of a hash set is unspecified, so without
sortedthe result can come out in any order, and the lesson's tests expect ascending order. - Checking against the wrong set. The second loop tests
seen, the numbers offirst. Testing againstintersectionSetwould always fail, because it starts empty. - Using an immutable set. With a plain
Set[Int](), the callseen += ionly compiles whenseenis avar, and each addition creates a new set. The mutable set is the right tool for this loop.
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, 0, 5],second = [5, -1, -1]gives[-1, 5].
