Swift HackerRank Missing Numbers Challenge

Question

I'm attempting to solve the "Missing Numbers" challenge on HackerRank where I'm tasked with finding missing elements comparing two arrays.

Foundation's NSCountedSet is a little pokey on large data sets, I rolled my counted set with a Swift Dictionary. I'm able to pass all the test cases with the exception of the last case which has ~10,000 elements in each array.

I looked through some of the comments for hints on how to complete the challenge, but they're all in other languages with uncommented code and non-descriptive variable naming.

// I put this in to save non-HackerRank users the hassle of getting inputs
let firstArrayCount = Int(readLine()!)! // unused
let listA = readLine()!.components(separatedBy: " ").map({Int(0ドル)!})
let secondArrayCount = Int(readLine()!)! // unused
let listB = readLine()!.components(separatedBy: " ").map({Int(0ドル)!})
// This is my method to create a countedSet
func countedSet(array: [Int]) -> Dictionary<Int, Int> {
 var dict = Dictionary<Int, Int>()
 for element in array {
 if dict[element] == nil {
 dict[element] = 1
 } else {
 dict[element] = dict[element]! + 1
 }
 }
 return dict
}
// Works fine on everything except large data sets
func missingNumbers(listA: [Int], listB: [Int]) -> String {
 var output: [Int] = []
 let comparisonSet = Set(listB) // list be is larger
 let ctdSetListA = countedSet(array: listA)
 let ctdSetListB = countedSet(array: listB)
 for element in comparisonSet {
 if ctdSetListA[element] != ctdSetListB[element] {
 output.append(element)
 }
 }
 return output.sorted().map({String(0ドル)}).joined(separator: " ")
}

I welcome suggestions on how to speed up my code. Thank you for reading.

Answer 1

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.

• Adrian: Thank you for such a detailed explanation of how to trim down my bloated code! Despite trimming it down, I'm still timing out on the the final test case.
• Martin R: @Adrian: See update :)
• Adrian: It appears not using Scanner was my bottleneck! I've learned many things with this question. Thank you!

Answer 2

An idea to solve this problem is the following

Sort A and B. Now we compare the elements of the list in that way

 i = j = 0
 while i < n and j < m 
 if A[i] != B[j] 
 print B[j] //We know that B[j] are not in A[i] because the numbers are sorted
 while j<m and B[j] == B[j+1] //Move j while B[j] equal to B[j+1], this is because we already count that number
 j = j+1
 else
 j = j + 1
 i = i + 1