0

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
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.

  • 1
    A hashtable has lookup time of O(1), except in degenerate cases. – Sebastian Redl Sep 13 at 10:08
  • Ummm, yeah. You are of course right. – Philip Kendall Sep 13 at 10:22
  • hmmm, what if i replace contains with binarySearch. – coroutineDispatcher Sep 13 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 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 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.