Why Map is my favorite data structure!
The data structure, which is just a simple combination of key-value pairs, can be your key to solving majority coding questions!
I recently started with May Leetcode Challenge, and so far almost all the questions that I solved were solved using maps! And that’s not it, maps can help you a lot in many tricky situations, especially during coding interviews.
When you are clueless about what to do? just give maps a try it is very likely that you will end up getting a solution. It won’t be perfect, it won’t be the most memory or time-efficient solution but, you’ll get an answer.
This can be the point between getting an offer and not getting an offer!
During my preparation for Amazon Interview, I went through hundreds of interview experience, I did the same during my Google Interview also!
And a whooping, 60%-70% of the questions could be solved using some implementation of maps.
Not only this, but many senior developers, interviewers, and my friends also have suggested Maps as the goto solution when you don’t have anywhere to go!
Some reasons why I feel Maps can be really helpful are:
- You can access data in O(1) time complexity
- Generally, in Tech Interviews there is more focus on minimizing time complexity compared to space. The map is the perfect candidate for this!
- Ease of accessing data, as a key can be literally anything!
What is a Map? Understanding it logically
A Map is a data structure in which we can store data in a format of key-value pairs.
To understand it more effectively let’s take an example of a hypothetical world. In this imaginary world, every person is associated with a Unique Identification number.
eg 8654956 -> John Doe (the unique ID of Mr. John Doe is 8654956)The organization that runs this hypothetical world is very insecure and tracks every person with a GPS, by using the Unique ID (sorry this world doesn’t have any concerns about your privacy).
So whenever they need to find any person, they just use the unique ID of that person and boom! They know where he/she is.
As this ID is unique for every person they can find any person within seconds and minimum efforts.
How does it work?
Map stores all the entries in a key-value format in table
_______________________
| KEY | VALUE |
-----------------------
| 1 | A |
-----------------------
| 2 | B |
-----------------------
| 456 | PQO |
-----------------------
| 789 | A |
|__________|_________ |Some rules that you must remember
- A key can not be repeated again (It must be unique)
- A value can be repeated many times
- The data type of key must be consistent. For a particular map, all the keys should be either an INT or STRING, etc. (Python Dictionary can have multiple Datatypes as key values, but it is not suggested that you do that)
That is the structure of a map. Whenever a new entry comes it is appended to the table. If the key is already present you can modify the current value.
But, I guess you can do all this with normal arrays and vectors also. Then why do you need a map for this?
Let me ask you some questions.
- Does array or vectors have the has_key or find or findKey method?
- Can you access the values with an index which is a string, char, object, or struct?
NO! you can not do all this with simple arrays or vectors!
In arrays and vectors data is stored serially so the index range from 0 to n. But, in a map, we define the index so we can access the index in O(1). And the map provides us with a function that can tell us whether a particular exists or not!
This is the biggest USP of Maps!
How to use it?
I’ll tell you some basic and important functions related to maps in the C++ language. The key logic behind these functions remains the same only their name and usage changes, so don’t worry if your favorite language is JAVA or Python. I’m sure you’ll figure it out by using the documentations.
- Libraries required
#include <bits/stdc++.h> //STL library (SUGGESTED)OR#include <map> //Only Map will be includedOR#include <unordered_map> //Only Unordered Map will be included
2. Defining a Map
The unordered map also follow a similar process
map<int, string> peopleTracker;
/*
key: int
value: string:
name of map: peopleTracker
*/3. Inserting data elements
Inserting Data is very similar to inserting data in an array or vector
peopleTracker[234] = "Mr John Doe";
/*
key: 234 and value:"Mr John Doe"
*/4. Key Collisions
Here comes the tricky part, what is the entry already exits? Don’t worry you’ll simply override the previous Data
peopleTracker[234] = "Mr Dane John";
/*
value changed from "Mr John Doe" -> "Me Dane John"
*/Now you want to check if there is an entry for some value or not. Here comes the find method!
if(peopleTracker.find(234) != peopleTracker.end())
cout << "Entry for 234 exits" << endl;mapName.find method will return a pointer to the end of the map if there is no entry with matching key, else it will point to the entry with the corresponding key!
To learn more about maps and hash-table refer to this cheatsheet which was suggested by Trey Huffine.
Now enough of knowledge, its time to practice!
Try to solve these seven problems on Leetcode.
Not all problems can be solved using a map, but figuring out where to use the map is also a skill! So go give your brains some exercise and try to solve these questions!
I hope you’ll understand where and how you can use maps and hash tables. With consistent practice, you’ll be able to master this data structure.
Thank you for reading!
Check out this excellent and interactive course on Data Structures and Algorithms in Python.
If you liked this blog don’t forget to signup for my newsletter! I promise you won’t be spammed.
Some of my other content that you might like!
Once again thank you for reading!
Happy Coding :)
