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

Question

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

Answer 1

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.