We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Naive solution will work O(n*m) time (for each word in rasom check that it is in magazine)
As an optimization we can sort magazine words first and then search will be faster, so O(m*log(m) + n*log(m)) = O((m+n)log(m)) and it should be faster for some cases (except when m >> n I believe), one can solve unequality to receive exact conditions for m, n.
As I can understand your solution works O(m+n) in average as soon as all operations are O(1) in average for hash table which is unordered_map (O(m*m + n*m) = O((m+n)*m) in the worst case which is almost impossible)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Hash Tables: Ransom Note
You are viewing a single comment's thread. Return to all comments →
Just as a reference about complexity:
Naive solution will work O(n*m) time (for each word in rasom check that it is in magazine)
As an optimization we can sort magazine words first and then search will be faster, so O(m*log(m) + n*log(m)) = O((m+n)log(m)) and it should be faster for some cases (except when m >> n I believe), one can solve unequality to receive exact conditions for m, n.
As I can understand your solution works O(m+n) in average as soon as all operations are O(1) in average for hash table which is unordered_map (O(m*m + n*m) = O((m+n)*m) in the worst case which is almost impossible)