DEV Community

Yukti Sahu
Yukti Sahu

Posted on

Hashmaps: My Ultimate Savior in the Wild World of DSA

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

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

Output:

2
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

💡 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;
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Dry Run (Because Visuals Help)

arr = [1, 3, 4, 2, 2]
Enter fullscreen mode Exit fullscreen mode

After the first loop → hashmap looks like this:

{1:1, 3:1, 4:1, 2:2}
Enter fullscreen mode Exit fullscreen mode

Second loop → finds that 2 has frequency 2.
✅ . Duplicate found.

Output:

Duplicate roll number: 2
Enter fullscreen mode Exit fullscreen mode

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:

  1. Understand the input and output → What are we working with?
  2. Find the logic and right data structure → What helps us solve it fastest?
  3. 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)