Maps are associative containers where values are mapped to their unique keys. The keys are sorted in ascending order by default.
Maps are widely used because of its freedom of datatype assignment. Also, the keys are assigned dynamically which results in better memory management than any trivial DS (like, arrays).
Map in C++ is one of the most important topics for Competitive Programming.
- Freedom of datatype assignment: The keys should be a set of any homogenous datatype (string, int, float) and the mapped values should be a set of another (or same) homogenous datatype.
- Keys are assigned dynamically: If you want 1000 as an Integer index (or key), a simple array would require you to allocate memory worth of 1000 integers. But, the same task using map will require a single integer block allocation.
You are given N strings as input. Print the frequency of all distinct strings encountered.
General Solution –
- A basic solution would be to run two loops and count the frequency of all strings encountered.
- Complexity: O(N * N)
Optimized solution –
- Maintain a Map with string datatype as the key and integer datatype as its mapped value.
- The idea is to map the count of string to the string itself. Whenever we encounter a string, we increment its mapped integer value. Now, if a string repeats itself, the count value will be incremented leaving us will the frequency of the string.
- Complexity: O(N)
using namespace std;
//Defining the map with key as a string and value as an integer
map <string, int> frequency_map;
//Number of strings
cin >> n;
for(int i = 0; i < n; i++)
cin >> input;
//Incrementing the count of inputted string
//Traversing the map
for(auto i = frequency_map.begin(); i != frequency_map.end(); i++)
// first value denoted the key while second denotes the value
cout << i->first << " : " << i->second << '\n';
Ayush : 1
Raman : 2
Rohit : 2
Comment out your feedback, suggestions or any mistakes. Hope it was a great learning session for you.
Do not forget to share and Subscribe.
Happy coding!! 🙂