The Beginning: Campus Placement Panic
So, my campus placements have officially started. And guess what? The moment I saw the word DSA on the prep list, I could literally hear my brain whispering, "Run!" 😂
But being the brave soul (and caffeine-powered coder) that I am, I decided to face it head-on. I opened a random problem, stared at it for 10 minutes like a detective at a crime scene, and then thought...
lol?
My Face
but one thing i know,
hashmaps can help. They always do something magical.
And yes, I was right.
So... What Exactly Is a Hashmap?
If you’re also like me — someone who used hashmaps before but didn’t really understand them — let’s clear that up.
A hashmap is like your brain’s quick memory. You remember your friend’s name (the key) and instantly recall their face (the value).
That’s exactly what hashmaps do — they store stuff in key-value pairs.
In C++, it’s called an unordered_map
.
you can also use ordered_map
as well.
Example Declaration:
unordered_map<int, int> m; // key: int, value: int
Some Common Operations:
m[key] = value; // Store a value
m[key]++; // Increment the frequency of key
m.find(key); // Check if key exists
m.erase(key); // Remove key-value pair
And the best part — all these operations are super fast, like O(1) average time. Pretty neat, right?
The Problem: "Lost Attendance Sheet" 📋
So here’s the story.
Imagine you’re a teacher, and you have a list of students’ roll numbers who attended class. Everything looks fine until... someone signs the attendance sheet twice! 😅
You now need to find which roll number is the duplicate.
Input:
[1, 3, 4, 2, 2]
Output:
2
Thinking Like a Problem Solver 🧠
Step 1: Understand Input and Output
- Input → an array of integers
- Output → the roll number that appears twice
Step 2: Think About the Logic
We need to count how many times each number appears.
If any number appears twice → that’s our culprit!
Step 3: Choose the Right Data Structure
We need quick insert + quick search = Hashmap ✅
Key → roll number
Value → frequency count
My First Attempt (aka the "Oops" moment)
unordered_map<int,int> m;
for(int i : arr) {
m[arr[i]]++;
}
for(auto i : m) {
if(m.second() >= 2) return m.first();
}
💡 Mistake alert! — I wrote m.second()
and m.first()
with brackets like they’re functions.
But nope — they’re members, not functions.
It should be:
if(i.second >= 2) return i.first;
Classic rookie move. Happens to the best of us. 😅
Final Working Code
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int findDuplicate(vector<int>& arr) {
unordered_map<int, int> m;
for (int i : arr) {
m[i]++;
}
for (auto i : m) {
if (i.second >= 2)
return i.first;
}
return -1; // no duplicate found
}
int main() {
vector<int> arr = {1, 3, 4, 2, 2};
cout << "Duplicate roll number: " << findDuplicate(arr);
return 0;
}
Dry Run (Because Visuals Help)
arr = [1, 3, 4, 2, 2]
After the first loop → hashmap looks like this:
{1:1, 3:1, 4:1, 2:2}
Second loop → finds that 2 has frequency 2.
✅ . Duplicate found.
Output:
Duplicate roll number: 2
All done in O(n) time, O(n) space.
Hashmaps doing their magic again 🪄
Why This Works
Normally, you’d have to compare every element with every other element → O(n²) time.
But hashmaps let you store and check everything in one pass → O(n) time.
Basically, they’re like the cheat codes of DSA problems.
Final Takeaway: How to Think in DSA
Over time, I’ve realized that solving DSA problems boils down to three things:
- Understand the input and output → What are we working with?
- Find the logic and right data structure → What helps us solve it fastest?
- Apply and tweak → Turn logic into working code, and fix when it doesn’t work (like my first attempt 😅)
The End (or Maybe Just the Beginning)
Hashmaps are that one friend in DSA who always has your back. They might look scary at first, but once you get them — oh boy, they make your life so much easier. 😎
So next time you feel lost in a jungle of arrays and strings, remember:
Hashmaps might just be your map 🗺️.
Top comments (0)