Hackerrank ransomnote

Question

This is the question; https://www.hackerrank.com/challenges/ctci-ransom-note/problem

I have solved this hacker rank challenge but i feel like the complexity is pretty inefficient because i use two nested loops which causes my program to run in quadratic time, i guess... I am sure there there is a better solution. Can someone tell me a better solution than what i have done. I'd also appreciate if i could get any feedback regarding my coding style or if there should be made any improvement to make it look more readable, better etc. Thank you.

function checkMagazine(magazine, note) {
  let isRansom=true
  note=note.split(' ')
  magazine=magazine.split(' ')

  for(let i of note){
    if(isRansom===false){
      console.log('No')
      return false;
    }
    else{
      for(let j of magazine){
        if(i===j){
          var index=magazine.indexOf(j)
          if(index>-1){ 
            magazine.splice(index,1)
          }
          isRansom=true;
          break;
        }
        else{
          isRansom=false;
        }
      }
    }
  }

  if(isRansom){
    return true
  }
}

checkMagazine('give me one grand today night','give me one grand today')

Answer 1

Having a look at the HackerRank problem, the title is implying a HashTable might be a nice data structure to use for this problem ("Hash Tables: Ransom Note"). You might want to look up more about the theory, some examples in JS, (and even more/reference). JS objects can also be used as HashMaps, with a discussion of the pros and cons of this in other SO answers.

Essentially, with a (Hash)Map we can associate keys of some type, with values of the same or another type. Such as mapping strings -> integers. Setting and looking up a value in a map is in constant O(1) time, whereas with an array, looking for a value (indexOf()) is in linear O(n) time. Using Map, the problem could be reduced to linear complexity. (Additionally, splice is an 'expensive' O(n) operation to remove an element from an array in JS).

Here is an idea / some pseudocode of how you might use a Map to solve the problem by mapping each word (string) to the count of how many occurrences we have of that word (integer).

map is an initially empty map

for every word in magazine:
    if word not in map:
        add word to map with count 1
    else:
        increment count of word in map

for every word in note:
    if word not in map or count of word in map = 0:
        show "No."
        return
    else:
        decrement count of word in map (word has been used)

show "Yes."
return

Ignoring the hashtables for a moment, your code is a bit unnecessarily complicated in places. We don't actually need two nested for-loops. Only one that goes through all words in note and removes them from magazine array as we use them up. This removes the need for all the nested if- conditions and the boolean flag isRansom. Finally, if you have something that looks like at the end of a function:

if(someBooleanValue) {
    return true;
}

This can be replaced by:

return someBooleanValue;

Check also the parameter and return types of the function: in the HackerRank problem, magazine and note are already string arrays, and the function is not expected to return a boolean value, merely print to the console. With that in mind, here is how it could be done:

function checkMagazine(magazine, note) {    
    for (let word of note) {
        let i = magazine.indexOf(word);

        if (i == -1) {
            console.log("No")
            return; 
        }     
        magazine.splice(i, 1);
    }

    console.log('Yes');
}

Note that despite there being no nested for-loops, it is still quadratic in complexity due to the outer loop (for every word in note), and the linear complexity of splice and indexOf inside this loop.