Hackerrank Sparse Arrays in Swift

Question

I solved this problem and was looking for feedback on my code. More efficient, cleaner, more verbose variable names, anything helps.

There are N strings. Each string's length is no more than 20 characters. There are also Q queries. For each query, you are given a string, and you need to find out how many times this string occurred previously.

import Foundation

func readIntegers() -> Int {
    return Int(readLine()!)!
}

func sparseArrays() {
    let numOfStrings = readIntegers()
    var arrayOfStrings = [String]()
    for _ in 0..<numOfStrings {
        let string = readLine()!
        arrayOfStrings.append(string)
    }
    let numOfQueries = readIntegers()
    for _ in 0..<numOfQueries {
        let singleString = readLine()!
        let arrayOfSingleString = arrayOfStrings.filter {$0 == singleString}
        print(arrayOfSingleString.count)
    }
}

sparseArrays()

Answer 1

func readIntegers() -> Int {
    return Int(readLine()!)!
}

Now this is confusing! A function called readIntegers which returns a single integer? readInteger() or readInt() would be an appropriate name.

The forced unwrapping is acceptable because the input comes from a programming challenge with well-defined input. However, finding errors in your code is easier if you check the optionals explicitly and print an descriptive error message if the input does not match the expectations.

And with a short description (using the "markdown format" which is recognized by the Xcode "Quick Help inspector") it becomes a reusable function for this and future programming challenges:

/// Returns an integer read from one line of standard input.
func readInteger() -> Int {
    guard let line = readLine() else {
        fatalError("Unexpected end of input")
    }
    guard let i = Int(line) else {
        fatalError("Invalid integer in input")
    }
    return i
}

The same for reading a single string:

/// Returns a string read from one line of standard input.
func readString() -> String {
    guard let line = readLine() else {
        fatalError("Unexpected end of input")
    }
    return line
}

I am (usually) not a fan of adding type information to a variable name, arrayOfStrings should just be named strings (as in the description of the challenge).

Instead of starting with an empty array and adding elements one can create the array with map(). This also allows us to declare the array as a constant:

let numOfStrings = readInteger()
let strings = (0..<numOfStrings).map {
    _ in readString()
}

singleString is better named query, and arrayOfSingleString is the array with all strings matching the query:

let numOfQueries = readInteger()
for _ in 0..<numOfQueries {
    let query = readString()
    let matchingStrings = strings.filter { $0 == query }
    print(matchingStrings.count)
}

We are only interesting in the count of matching elements. To improve the performance, determine the count without creating an intermediate array:

    let matchingCount = strings.reduce(0) { (accum, str) in
        accum + (str == query ? 1 : 0)
    }
    print(matchingCount)

Another speed-up could be achieved by

• Sorting the given strings, this needs to be done only once.
• Use binary search to find a query string in the array.
• If the string is found, traverse forward and backward through the array to determine how many strings are equal to the query string.