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

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

Philip Kendall · Accepted Answer · 2019-09-13T10:22:13.030

3

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.

edited Sep 13 '19 at 10:22

answered Sep 13 '19 at 10:02

Philip Kendall

22,899
9
58
61

1

A hashtable has lookup time of O(1), except in degenerate cases. – Sebastian Redl Sep 13 '19 at 10:08
Ummm, yeah. You are of course right. – Philip Kendall Sep 13 '19 at 10:22
hmmm, what if i replace `contains` with `binarySearch`. – coroutineDispatcher Sep 13 '19 at 10:24
@coroutineDispatcher That would make it a lot faster, assuming the array in question is sorted. Still might not be faster than a hash map. – Sebastian Redl Sep 13 '19 at 10:32
2

@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 '19 at 12:24

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

1 Answers1