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.
I used the map function in C++ with every string mapped to their occurence. Once I stored everything to the map I can just extract the number of occurences and print it out.
What does it mean? Could you explain it in detail? What is a map in C++, how to implement it, what is being mapped and to what? Would be really helpful. Thanks :)
hi @abhinavkanoria , Map in C++ is associative containers that store elements formed by a combination of a key value and a mapped value. You can see the rest explanation from here ->
None of these solutions are O(n), actually. You have to take into consideration the time it takes to read a string, O(c), where c is the number of characters in the string.
You're partly right and partly wrong. These are indeed O(N) [or really, O(N+M)], assuming O(C) is constant, which it is if C is bound -- an often reasonable assumption.
These days, though, strings can sometimes be extraordinarily long, so it is an important point to keep in mind, in which case it's O(N*C) [or really O(N*C + M), assuming you optimize by hashing each string]. For example, it's not unusual to run a regular expression on arbitrary input, and the input can be many megabytes long -- in which case grepstrings that used to work just fine fail spectacularly. I learned this the hard way!
Sparse Arrays
You are viewing a single comment's thread. Return to all comments →
I used the map function in C++ with every string mapped to their occurence. Once I stored everything to the map I can just extract the number of occurences and print it out.
This is exactly what I did. Bonus points if you used the unordered version since ordering isn't needed here.
What does it mean? Could you explain it in detail? What is a map in C++, how to implement it, what is being mapped and to what? Would be really helpful. Thanks :)
hi @abhinavkanoria , Map in C++ is associative containers that store elements formed by a combination of a key value and a mapped value. You can see the rest explanation from here ->
http://www.cplusplus.com/reference/map/map/
My submission below is the implementation of Map to solve the challenge -> https://www.hackerrank.com/challenges/sparse-arrays/submissions/code/19558681
Yes and this approach is actually O(n) unlike some comments above who have achieved this in O(n^2)
None of these solutions are O(n), actually. You have to take into consideration the time it takes to read a string, O(c), where c is the number of characters in the string.
You're partly right and partly wrong. These are indeed O(N) [or really, O(N+M)], assuming O(C) is constant, which it is if C is bound -- an often reasonable assumption.
These days, though, strings can sometimes be extraordinarily long, so it is an important point to keep in mind, in which case it's O(N*C) [or really O(N*C + M), assuming you optimize by hashing each string]. For example, it's not unusual to run a regular expression on arbitrary input, and the input can be many megabytes long -- in which case grepstrings that used to work just fine fail spectacularly. I learned this the hard way!