LeetCode - Hash Map / Set - Two Sum/ Contains Duplicates/ Top K Frequent Element

🔷 Problem 1: Two Sum (LeetCode #1)

Find two numbers that add up to the target. Return their indices.

🧾 Input:

nums = [2, 7, 11, 15], target = 9

✅ Output:

[0, 1]  // because 2 + 7 = 9

---

❌ Brute Force (O(n²)):

vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
        for (int j = i + 1; j < nums.size(); ++j)
            if (nums[i] + nums[j] == target)
                return {i, j};
    return {};
}

---

✅ Optimized with unordered_map (O(n)):

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map; // value -> index
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (map.count(complement))
            return {map[complement], i};
        map[nums[i]] = i;
    }
    return {};
}

---

📊 Iteration Table

i	nums[i]	target - nums[i]	map (val → idx)	Action
0	2	7	{}	Store 2 → 0
1	7	2	{2 → 0}	Found! return [0, 1]

---

---

🔷 Problem 2: Contains Duplicate (LeetCode #217)

Return true if any number appears more than once.

🧾 Input:

nums = [1, 2, 3, 1]

✅ Output:

true

---

❌ Brute Force (O(n²)):

bool containsDuplicate(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 with unordered_set (O(n)):

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

---

📊 Iteration Table

i	nums[i]	seen set	Action
0	1	{}	Insert 1
1	2	{1}	Insert 2
2	3	{1, 2}	Insert 3
3	1	{1, 2, 3}	Found duplicate → true

---

---

🔷 Problem 3: Top K Frequent Elements (LeetCode #347)

Return the k most frequent elements.

🧾 Input:

nums = [1,1,1,2,2,3], k = 2

✅ Output:

[1, 2]

---

❌ Brute Force (O(n²)):

• Count manually using nested loops and sort.

---

✅ Optimized with unordered_map + Min Heap (O(n log k)):

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int n : nums) freq[n]++;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    for (auto& [num, count] : freq) {
        minHeap.push({count, num});
        if (minHeap.size() > k)
            minHeap.pop();
    }

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    return result;
}

---

📊 Iteration Table (frequency map)

num	freq[num]	freq map
1	1	{1:1}
1	2	{1:2}
1	3	{1:3}
2	1	{1:3, 2:1}
2	2	{1:3, 2:2}
3	1	{1:3, 2:2, 3:1}

---

🔚 Summary Table

Problem	Brute Time	Best Time	Structure	STL Container
Two Sum	O(n²)	O(n)	val → index	unordered_map
Contains Duplicate	O(n²)	O(n)	seen check	unordered_set
Top K Frequent Elements	O(n² log n)	O(n log k)	freq count + PQ	unordered_map, heap

---

🔷 Problem 4: Group Anagrams (LeetCode #49)

Group strings that are anagrams of each other.

---

🧾 Input:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

✅ Output:

[["eat","tea","ate"],["tan","nat"],["bat"]]

---

❌ Brute Force (O(n² * k log k)):

• Compare every string with every other using sorting.

---

✅ Optimized using unordered_map<string, vector<string>>:

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;
    for (string& s : strs) {
        string key = s;
        sort(key.begin(), key.end()); // Sorted string as key
        map[key].push_back(s);
    }

    vector<vector<string>> result;
    for (auto& [key, group] : map) {
        result.push_back(group);
    }
    return result;
}

---

📊 Iteration Table

str	Sorted Key	Map (key → list of anagrams)
"eat"	"aet"	{"aet": ["eat"]}
"tea"	"aet"	{"aet": ["eat", "tea"]}
"tan"	"ant"	{"aet": [...], "ant": ["tan"]}
"ate"	"aet"	{"aet": [..., "ate"], "ant": [...]}
"nat"	"ant"	{"aet": [...], "ant": ["tan","nat"]}
"bat"	"abt"	{"...": ..., "abt": ["bat"]}

---

🔷 Problem 5: Subarray Sum Equals K (LeetCode #560)

Count the number of subarrays whose sum equals k.

---

🧾 Input:

nums = [1, 1, 1], k = 2

✅ Output:

2  // Subarrays [1,1] and [1,1]

---

❌ Brute Force (O(n²)):

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        int sum = 0;
        for (int j = i; j < nums.size(); j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

---

✅ Optimized using Prefix Sum + unordered_map<int, int>

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixSum;
    prefixSum[0] = 1;  // base case: sum 0 has 1 occurrence
    int sum = 0, count = 0;

    for (int num : nums) {
        sum += num;
        if (prefixSum.count(sum - k))
            count += prefixSum[sum - k];
        prefixSum[sum]++;
    }
    return count;
}

---

📊 Iteration Table

i	num	sum	sum - k	prefixMap	count
0	1	1	-1	{0:1}	0
1	1	2	0	{0:1,1:1}	1
2	1	3	1	{0:1,1:1,2:1}	2

---

🔷 Problem 6: Longest Consecutive Sequence (LeetCode #128)

1.  ✅ Brute Force — O(n²)

2. ✅ Optimal Solution — O(n) using unordered_set

---

🔴 Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

• You must write an algorithm that runs in O(n) time.

Example:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest sequence is [1, 2, 3, 4]

---

🧪 1. Brute Force Approach — O(n²)

✅ Idea:

• For every number x, check if x+1, x+2, ..., exist in the array.

• Use std::find() or loop to check existence.

🔧 Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    int longest = 0;
    for (int i = 0; i < nums.size(); ++i) {
        int currentNum = nums[i];
        int count = 1;
        
        while (find(nums.begin(), nums.end(), currentNum + 1) != nums.end()) {
            currentNum += 1;
            count += 1;
        }
        
        longest = max(longest, count);
    }
    return longest;
}

🧠 Iteration Example:

Input: [100, 4, 200, 1, 3, 2]

1. i = 0 → 100 → next = 101 ❌ → count = 1

2. i = 1 → 4 → 5 ❌ → count = 1

3. i = 2 → 200 → 201 ❌ → count = 1

4. i = 3 → 1 → 2 ✅ → 3 ✅ → 4 ✅ → 5 ❌ → count = 4 ✅

5. i = 4 → 3 → 4 ✅ → 5 ❌ → count = 2 ❌

6. i = 5 → 2 → 3 ✅ → 4 ✅ → 5 ❌ → count = 3 ❌

👉 Max count = 4

⛔ Time Complexity: O(n²) because find() is O(n) in a loop

---

✅ 2. Optimal Solution — O(n) using unordered_set

✅ Idea:

1. Insert all numbers into a set (for O(1) lookup).

2. For each number x, check if x-1 exists:

   • If not, it's the start of a sequence.

   • Count how long the sequence goes: x+1, x+2, ...

3. Track the max sequence length.

🔧 Code:

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longest = 0;

    for (int num : numSet) {
        // Only start counting if it's the start of a sequence
        if (!numSet.count(num - 1)) {
            int currentNum = num;
            int count = 1;

            while (numSet.count(currentNum + 1)) {
                currentNum += 1;
                count += 1;
            }

            longest = max(longest, count);
        }
    }
    return longest;
}

---

🧠 Iteration Example:

Input: [100, 4, 200, 1, 3, 2]
Set = {1, 2, 3, 4, 100, 200}

1. Iteration	num	numSet.count(num - 1)	Is Start of Sequence?	Counted Sequence	count	longest
   1	100	numSet.count(99) = ❌	✅ Yes	100	1	1
   2	4	numSet.count(3) = ✅	❌ No	—	-	1
   3	200	numSet.count(199) = ❌	✅ Yes	200	1	1
   4	1	numSet.count(0) = ❌	✅ Yes	1 → 2 → 3 → 4	4	4
   5	3	numSet.count(2) = ✅	❌ No	—	-	4
   6	2	numSet.count(1) = ✅	❌ No	—	-	4

✅ Max sequence: 4

---

⏱ Time & Space:

• Time: O(n)

• Space: O(n)

---

✅ Final Thoughts

Approach	Time	Space	Use When...
Brute Force	O(n²)	O(1)	Just learning or small inputs
Optimal (Set)	O(n)	O(n)	Required for LeetCode constraints

---