The "create or update" in the countedSet function
can be simplified using the nil-coalescing operator ??:
func countedSet(array: [Int]) -> Dictionary<Int, Int> {
var dict = Dictionary<Int, Int>()
for element in array {
dict[element] = (dict[element] ?? 0) + 1
}
return dict
}
This also saves one dictionary lookup if the value is already present in the dictionary.
I would (but that may be a matter of personal preference) separate the string
conversion completely from the difference computation. Return an integer
array from missingNumbers:
func missingNumbers(listA: [Int], listB: [Int]) -> [Int]
and do the string conversion at the call site:
let missing = missingNumbers(listA: listA, listB: listB)
print(missing.map({String($0)}).joined(separator: " "))
or print the numbers directly, without string conversion:
let missing = missingNumbers(listA: listA, listB: listB)
for num in missing {
print(num, terminator: " ")
}
print()
The comparisonSet in the missingNumbers function is not needed. Since B is
the "larger" set, it suffices to iterate over the counted set generated from B:
func missingNumbers(listA: [Int], listB: [Int]) -> [Int] {
var output: [Int] = []
let ctdSetListA = countedSet(array: listA)
let ctdSetListB = countedSet(array: listB)
for (element, count) in ctdSetListB {
if ctdSetListA[element] != count {
output.append(element)
}
}
return output.sorted()
}
The next improvement is to use only one counted set: Add the elements from B
and subtract the elements from A. Then check which elements have a positive count
in the end:
func missingNumbers(listA: [Int], listB: [Int]) -> [Int] {
var ctdSet = countedSet(array: listB)
for element in listA {
ctdSet[element]! -= 1 // We know that elements in A are present in B
}
let output = ctdSet.filter { $0.value > 0 }.map { $0.key }
return output.sorted()
}
Generally, a "filter + map" operation can be optimized with flatMap:
let output = ctdSet.flatMap { $0.value > 0 ? $0.key : nil }
The essential clue however is (I assume) the given constraint
The difference between maximum and minimum number in B is less than or equal to 100.
which means that we can use a fixed sized array to keep track of the number of
occurrences of each number, and all
dictionary lookups now become "simple" array subscript operations.
This also makes sorting the missing numbers redundant:
func missingNumbers(listA: [Int], listB: [Int]) -> [Int] {
guard let minValue = listB.min() else { return [] } // Empty input
var counts = Array(repeating: 0, count: 101)
for elem in listB {
counts[elem - minValue] += 1
}
for elem in listA {
counts[elem - minValue] -= 1
}
var output: [Int] = []
for i in counts.indices {
if counts[i] > 0 {
output.append(i + minValue)
}
}
return output
}
The final for loop creating the output array also can be written concisely in a functional
way as
let output = counts.enumerated().flatMap { $0.element > 0 ? $0.offset + minValue : nil }
Another possible performance bottleneck is when the input data is read:
let listA = readLine()!.components(separatedBy: " ").map({Int($0)!})
The input lines can contain up to 1,000,010 integers, which means
that many temporary string are created. An alternative is to use
Scanner from the Foundation framework to read integers directly
from the string. And since the number of integers is known, we
can call reserveCapacity() to avoid reallocations while the
array grows:
func splitToIntegers(_ s: String, count: Int) -> [Int] {
var result: [Int] = []
result.reserveCapacity(count)
var n = 0
let scanner = Scanner(string: s)
while scanner.scanInt(&n) {
result.append(n)
}
return result
}
let firstArrayCount = Int(readLine()!)!
let listA = splitToIntegers(readLine()!, count: firstArrayCount)
let secondArrayCount = Int(readLine()!)!
let listB = splitToIntegers(readLine()!, count: secondArrayCount)
This turned out to be much faster in my test.
