Problem overview
The method intersection receives two integer arrays, first and second. It returns an array of the numbers that appear in both. Each number is listed once, however many times it appears in the inputs, and the result is sorted in ascending order.
For first = [1, 2, 2, 1] and second = [2, 2], only 2 is shared, so the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4], the numbers 4 and 9 are shared. Each appears twice in second but once in the result, and the ascending order gives [4, 9].
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 direct way is to check each number of second against every number of first, which takes O(n × m) comparisons. The cost comes from searching an array for a value one element at a time.
A Set answers "is this number in here?" in constant time on average. It also stores each value only once, which is the other half of the requirement. So:
- Put every number of
firstinto a set calledseen. - Walk through
second. Whenever a number is inseen, it is in both arrays, so put it into a second set,intersectionSet. - Turn
intersectionSetinto a sorted array.
Duplicates need no extra code. Inserting a value that is already in a set changes nothing, so a number that repeats in either input still ends up in the result once.
The last step matters. A set has no order of its own, and the order in which its elements come out can change from one run to another, so the result has to be sorted explicitly.
Step by step
- Name the inputs.
nums1andnums2are constants that refer tofirstandsecond. Shorter names make the loops easier to read, and nothing is copied in any meaningful way. - Create an empty set
seenwithvar seen = Set<Int>(). It is avarbecause elements will be added to it. - Loop over
nums1withfor i in nums1. Every number of the first array must be inseenbefore the second array is examined. - Insert each number with
seen.insert(i). Repeats are harmless. - Create a second empty set,
intersectionSet, for the shared numbers. A set keeps each shared number once, as the answer requires. - Loop over
nums2, checking its numbers one at a time againstseen. - Test membership. If
seen.contains(i), insertiintointersectionSet. A shared number that appears twice innums2is stored once. - Return the sorted set.
intersectionSet.sorted()returns an array of the elements in ascending order.
The solution in Swift
class Solution {
func intersection(_ first: [Int], _ second: [Int]) -> [Int] {
let nums1 = first
let nums2 = second
var seen = Set<Int>()
for i in nums1 {
seen.insert(i)
}
var intersectionSet = Set<Int>()
for i in nums2 {
if seen.contains(i) {
intersectionSet.insert(i)
}
}
return intersectionSet.sorted()
}
}
The Swift details worth a closer look:
Set<Int>()creates an empty set of integers. The element type has to be hashable, whichIntis.insertreturns a value you can ignore. It returns a tuple saying whether the element was new and which member is in the set. Forvar s = Set<Int>(),s.insert(3)reportsinserted: truethe first time andinserted: falsethe second. Swift'sinsertis marked so that dropping that result produces no warning.sorted()on a set returns an[Int]. The result ofSet([3, 1, 2]).sorted()is the array[1, 2, 3], which is exactly the return type of the method. A set itself is not an array and can't be returned as one.- Set order is unspecified. Looping over a set directly, or turning it into an array without
sorted(), can give a different order from run to run. Sorting at the end removes that uncertainty. - Arrays are values.
let nums1 = firstdoesn't create a linked second name that could be changed through the first. Because the code never changes either array, nothing is lost.
Complexity
Time: O(n + m) plus the sort. Building seen takes n insertions, and the second loop does at most m lookups and insertions. Each set operation takes constant time on average. The final sorted() costs O(k log k), where k is the number of shared values, and k is at most the smaller of the two lengths.
Space: O(n + m). seen holds up to n values, intersectionSet holds up to min(n, m), and the returned array has k elements.
Edge cases and common mistakes
- No shared numbers.
[1, 2, 3]and[4, 5, 6]give[], an empty array. - Negative numbers and zero.
[-1, 0, -1]and[0, -1, -1, 5]give[-1, 0]. Sets treat negative values like any other, and the sort puts-1before0. - Duplicates on either side. They don't change the result. Using an array for
intersectionSetand appending without a check would list a number once per match. - Forgetting to sort. Returning
Array(intersectionSet)compiles and holds the right numbers, but their order isn't guaranteed, so the answer can come out as[9, 4]where[4, 9]is expected. - Checking against the wrong array. The set has to be completely built from
nums1before the loop overnums2starts. Mixing both in one loop would miss pairs where the shared number appears first insecond. - Searching the array. Using
first.contains(i)inside the loop works and gives the same answer, but each call scans the whole array, which brings back theO(n × m)cost.
Testing
first = [1, 2, 2, 1],second = [2, 2]returns[2].first = [4, 9, 5],second = [9, 4, 9, 8, 4]returns[4, 9].first = [1, 2, 3],second = [4, 5, 6]returns[].first = [-1, 0, -1],second = [0, -1, -1, 5]returns[-1, 0].
