LeetCode - unodered_map unordered_set - Frequency Count/ Duplicates Check/ Element Lookups

🧮 1. Frequency Count

Problem: Given an array of integers, return the frequency of each number.

🔹 Input:

nums = {4, 5, 6, 4, 5, 4};

🔹 Output:

4: 3
5: 2
6: 1

---

🔸 Brute Force:

void frequencyBruteForce(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        int count = 0;
        for (int j = 0; j < nums.size(); j++) {
            if (nums[i] == nums[j])
                count++;
        }
        cout << nums[i] << ": " << count << endl;
    }
}

🔸 Optimized (unordered_map):

void frequencyOptimized(vector<int>& nums) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    for (auto& [key, value] : freq) {
        cout << key << ": " << value << endl;
    }
}

📊 Iteration Table:

Iteration	num	freq map
1	4	{4: 1}
2	5	{4: 1, 5: 1}
3	6	{4: 1, 5: 1, 6:1}
4	4	{4: 2, 5: 1, 6:1}
5	5	{4: 2, 5: 2, 6:1}
6	4	{4: 3, 5: 2, 6:1}

---

🔁 2. Check Duplicates

Problem: Given an array, check if any element appears more than once.

🔹 Input:

nums = {1, 2, 3, 1};

🔹 Output:

true

---

🔸 Brute Force:

bool hasDuplicateBruteForce(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] == nums[j])
                return true;
        }
    }
    return false;
}

🔸 Optimized (unordered_set):

bool hasDuplicateOptimized(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num))
            return true;
        seen.insert(num);
    }
    return false;
}

📊 Iteration Table:

Iteration	num	seen set	Duplicate Found
1	1	{1}	No
2	2	{1,2}	No
3	3	{1,2,3}	No
4	1	{1,2,3}	Yes ✅

---

🔍 3. Element Lookup

Problem: Check if a given target exists in the array.

🔹 Input:

nums = {10, 20, 30, 40};
target = 30;

🔹 Output:

true

---

🔸 Brute Force:

bool findBruteForce(vector<int>& nums, int target) {
    for (int num : nums) {
        if (num == target)
            return true;
    }
    return false;
}

🔸 Optimized (unordered_set):

bool findOptimized(vector<int>& nums, int target) {
    unordered_set<int> s(nums.begin(), nums.end());
    return s.count(target) > 0;
}

📊 Iteration Table for Building Set:

Iteration	num	set
1	10	{10}
2	20	{10, 20}
3	30	{10, 20, 30}
4	40	{10,20,30,40}

Then:

Lookup: s.count(30) → true ✅

---

Summary

Use Case	Brute Force Time	Optimized Time	Data Structure
Frequency Count	O(n²)	O(n)	unordered_map<int,int>
Duplicates	O(n²)	O(n)	unordered_set<int>
Lookup	O(n)	O(1)	unordered_set<int>