Do I have do use HashTables/Maps/Hashmaps in this algorithm?

I am doing the Ransom Note algorithm in Hackerrank. The thing is I am not using maps and all the tests pass except for three which execution time takes a lot more. (Kotlin language) I have two approaches:

1 - Recursively

``````fun checkMagazine(magazine: Array<String>, note: Array<String>): Unit {
controlWords(magazine, 0, magazine.size / 2, note)
controlWords(magazine, magazine.size / 2 + 1, magazine.size - 1, note)

if (note.none { it.isNotEmpty() }) print("Yes") else print("No")
}

fun controlWords(magazine: Array<String>, start: Int, end: Int, note: Array<String>) {
if (end - start < 1) {
return
}

for (j in start..end) {
if (note.none { value -> value.isNotEmpty() }) {
return
}
if (note.contains(magazine[j])) note[note.indexOf(magazine[j])] = ""
}
}
``````

And Iteratively:

``````magazine.map {
if (note.none { value -> value.isNotEmpty() }) {
print("Yes")
return
}
if (note.contains(it)) note[note.indexOf(it)] = ""
}

if (note.none { it.isNotEmpty() }) print("Yes") else print("No")
``````

Obviously it pushes me to use maps, but can there be another solution, faster, without maps?

Your code did not execute within the time limits

• Why are you against using a map, the right solution for this problem? – Philip Kendall Sep 13 at 10:34
• No, nothing particular. I just wanted to see the result without hashmaps – coroutineDispatcher Sep 13 at 10:46

In both cases, you have an O(n^2) algorithm - you have a loop (either explicitly in your recursive case or implicitly as part of `map` in the iterative case) which calls `contains`. `contains` has to iterate over the entire array to determine it's result, so it's going to be slow. A map has a lookup time of O(1) so will be a lot quicker.
• hmmm, what if i replace `contains` with `binarySearch`. – coroutineDispatcher Sep 13 at 10:24
• @coroutineDispatcher: Note that your repeated `note.none(…)` calls are also slow. They have to iterate over the entire `note` array in the worst case. – Bart van Ingen Schenau Sep 13 at 12:24