0

I implemented a simple algorithm in 2 ways. One using indexOf and other one using Hash Table.

The problem: Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

First one. Is it Time Complexity O(N^2) because I have N letters in the ransomNote and I can do N searches in the indexOf?

var canConstruct = function(ransomNote, magazine) {
    if(magazine.length < ransomNote.length) return false;
    
    const arr = magazine.split("");
    for(let i=0; i<ransomNote.length; i++) {
        if(arr.indexOf(ransomNote[i]) < 0)
            return false;
        const index = arr.indexOf(ransomNote[i]);
        arr.splice(index, 1);
    }
    
    return true;
};

Second one. What is the time complexity? Does the hash table makes it O(N)?

var canConstruct = function(ransomNote, magazine) {
    if(magazine.length < ransomNote.length) return false;
    
    const map = new Map();
    for(let i =0; i<magazine.length; i++) {
        if(map.has(magazine[i]))
            map.set(magazine[i], map.get(magazine[i])+1);
        else
            map.set(magazine[i], 1);
    }
    
    for(let i=0; i<ransomNote.length; i++) {
        if(!map.has(ransomNote[i]))
            return false;
        else {
            const x = map.get(ransomNote[i]) - 1;
            if(x > 0)
                map.set(ransomNote[i], x)
            else
                map.delete(ransomNote[i]);
        }
    }
    
    return true;
};

Thanks

Improve this question

2 Answers 2

Reset to default
1

FIRST solution

Well one thing you have to take in consideration, especially in the first solution is that split, slice and indexOf methods all have their own time complexity.

Let's say you have m letters in magazine. When you split it into array, you will already use O(m) time complexity there (and of course O(m) space complexity due to the fact you store it all in a new array, that has a size of m).

Now you enter a for loop that will run n times (where n is the number of letters in ransomNote). So right then and there you have O(m * n) time complexity. indexOf operation will also be called n times with the caveat that it runs O(m) every time it's called. You can see there how quickly you start adding up your time complexity.

I see it being like O(3 * m * n^2) which rounds up to O(m * n^n) time complexity. I would strongly suggest not calling indexOf multiple times, just call it once and store its result somewhere. You will either have an index or -1 meaning it wasn't found.

SECOND solution

Much better. Here you populate a hash map (so some extra memory used, but considering you also used a split in first, and stored it, it should roughly be the same).

And then you just simply go with one loop over a randomNote and find a letter in the hashMap. Finding a letter in map is O(1) Time so it's really useful for this type of algorithm.

I would argue the complexity would be O(n * m) in the end so much better than the first one.

Hope I made sense to you. IF you want we can dive a bit deeper in space analysis later in the comments if you respond

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you, very well explained. Do you mind explaining why finding a letter in HashMap is O(1)? Also, you said for the second solution it would be O(N*M). If N and M can both be infinity, isn't it same as O(N) where N is the number of letters of the biggest string?
Here is a very relevant post about hash map lookups being a O(1) time operation. In my opinion they probably use something like an array of linked lists where the lookup is really fast but you can read more about it here: stackoverflow.com/questions/48603244/… As for the other part, the reason it is O(nm) and not O(n) is because n and m represent different things. I am not saying that they can't both be infinite, but one can also have only one letter and other be infinite so it is more accurate to say O(nm) :)
Awesome! Thank you
1

The version with indexOf() is O(N*M), where N is the length of the ransom note, and M is the length of the magazine. You perform up to N searches, and each search is linear through the magazine array that's N characters. Also, array.splice() is O(M) because it has to copy all the array elements after index to the lower index.

Hash table access and updates are generally considered to be O(1). The second version performs N hash table lookups and updates, so the overall complexity is O(N).

Improve this answer

1 Comment

Thank you. Are you saying that the first one is O(N*M) and not O(N^2) ?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.