Problem overview
The method findDuplicates receives an array of integers and returns a new array with the values that appear more than once. Each duplicated value should be listed once, in any order. For [2, 3, 1, 1, 4, 3, 2, 1], the values 2, 3 and 1 each appear at least twice (the 1 appears three times), while 4 appears once. The answer holds 2, 3 and 1.
The statement asks for O(n) time and O(n) extra space.
Approach: count as you go
Comparing every pair of elements would take O(n²). A dictionary from each value to the number of times it has been seen avoids that: one pass is enough, and each update takes constant time on average.
The detail that matters is when to add a value to the result. A value that appears three times reaches the counts 1, 2 and 3 in turn. Adding it every time the count is above one would list it twice. Adding it at the moment the count becomes exactly 2 records it once, no matter how many more copies follow. A value that never reaches 2 is never recorded.
Step by step
- Create
result, an empty[Int], to collect the duplicates. - Create
freq, an empty[Int: Int], mapping each number to how many times it has appeared. - Loop over
numswith the variablevalue, so every number is counted. - Increase the count with
freq[value, default: 0] += 1. Thedefault: 0subscript supplies 0 for a number seen for the first time, so no separate "is the key there?" check is needed. - Test for exactly 2.
if freq[value] == 2is true at the single moment a value is discovered to be a duplicate. - Append it to
resultinside thatif. - Return
result.
Tracing the example
For [2, 3, 1, 1, 4, 3, 2, 1] the counts grow as follows. The values 2, 3 and 1 get their first count of 1, and nothing is appended. The second 1 (index 3) raises its count to 2, so 1 is appended. The 4 is counted once. The second 3 (index 5) reaches 2, so 3 is appended. The second 2 (index 6) reaches 2, so 2 is appended. The last 1 raises its count to 3, which isn't 2, so nothing happens. The result is [1, 3, 2].
The solution in Swift
class Solution {
func findDuplicates(_ nums: [Int]) -> [Int] {
var result = [Int]()
var freq = [Int: Int]()
for value in nums {
freq[value, default: 0] += 1
if freq[value] == 2 {
result.append(value)
}
}
return result
}
}
Swift details worth a closer look:
- Optional lookups. A plain
freq[value]has the typeInt?, because the key might be missing. Thedefault:subscript returns a non-optionalIntand can be used with+=; it writes the new count back into the dictionary. - Comparing an optional with a literal.
freq[value] == 2compares anInt?with an integer without unwrapping it. Swift treats the literal as an optional too, so the comparison is true when the value exists and equals 2, and false when it isnil. Here the key was just updated, so it always exists. - Value types. The dictionary and the array are value types, which is why both are declared with
var: the loop changes them. - Order of the result. Values are appended in the order their second copy appears. For the example, the second 3 comes before the second 1 and the second 2, so the method returns
[1, 3, 2](the 1 reaches its second copy at index 3, the 3 at index 5, the 2 at index 6). The statement allows any order.
An alternative with two sets
The same idea can use sets instead of counts. One set records values seen, and a second records values already reported:
func dups(_ nums: [Int]) -> [Int] {
var seen = Set<Int>()
var reported = Set<Int>()
var result = [Int]()
for value in nums {
if !seen.insert(value).inserted && reported.insert(value).inserted {
result.append(value)
}
}
return result
}
A value is appended when its insert into seen fails (an earlier copy exists) and its insert into reported succeeds (this is the first time it is reported). It also returns [1, 3, 2] for the example, with the same O(n) bounds. The counting version is the one to prefer when you may later need the counts themselves.
Complexity
Time: O(n). One pass; each dictionary read, update and array append takes constant time on average.
Space: O(n). The dictionary holds one entry per distinct value, and the result holds at most n / 2 values.
Edge cases and common mistakes
- No duplicates.
[1, 2, 3]returns[]. - Many copies.
[5, 5, 5, 5]returns[5], not four 5s. That is what the exact test for 2 guarantees. Testingfreq[value]! >= 2would append the value on every extra copy. - Empty array. The loop doesn't run, and the result is
[]. - Force-unwrapping before inserting. Writing
freq[value]! += 1for a new key crashes the program, since the value isnil. Thedefault:form avoids that. - Comparing results. Since any order is accepted, sort both sides before comparing against an expected array.
Testing
[2, 3, 1, 1, 4, 3, 2, 1]gives[1, 3, 2].[5, 5, 5, 5]gives[5].[1, 2, 3]gives[].
