Hash Maps

Introduction

Hash maps (also called hash tables or dictionaries) are among the most versatile and frequently used data structures in programming. They provide near-constant time lookups, insertions, and deletions, making them invaluable for optimizing algorithms and solving complex problems efficiently.

In this comprehensive guide, we’ll explore essential hash map patterns through practical problems with clean, optimized solutions in both C# and Python.

What is a Hash Map?

A hash map is a data structure that stores key-value pairs and provides:

• O(1) average-case lookup: Find values by key instantly
• O(1) average-case insertion: Add new key-value pairs quickly
• O(1) average-case deletion: Remove entries efficiently

How Hash Maps Work

1. Hash function converts keys into array indices
2. Values are stored at computed indices
3. Collisions are handled via chaining or open addressing

Common Use Cases

• Counting frequencies
• Caching and memoization
• Tracking seen elements
• Grouping related data
• Complement/pair finding

Problem 1: Two Sum

Difficulty: Easy
Tags: Hash Map, Array

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9, so we return [0, 1]

Approach: Hash Map for Complement Lookup

Instead of checking every pair (O(n²)), store each number’s complement and check if the current number exists as a complement.

Key Insight: For each number x, we need to find target - x. Store target - x as we iterate.

C# Solution

public class Solution 
{
    public int[] TwoSum(int[] nums, int target) 
    {
        // Map stores: complement -> index
        Dictionary<int, int> complementMap = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) 
        {
            // Check if current number is a complement of a previous number
            if (complementMap.ContainsKey(nums[i])) 
            {
                return new int[] { complementMap[nums[i]], i };
            }
            
            // Store the complement needed for current number
            int complement = target - nums[i];
            complementMap[complement] = i;
        }
        
        return new int[] { };
    }
}

Python Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        complement_map = {}
        
        for i, num in enumerate(nums):
            # Check if current number is a complement
            if num in complement_map:
                return [complement_map[num], i]
            
            # Store complement needed for current number
            complement = target - num
            complement_map[complement] = i
        
        return []

Time Complexity: O(n)
Space Complexity: O(n)

Key Insights

• Hash map trades space for time (O(n) space for O(n) time)
• Single pass through array is sufficient
• Store what you’re looking for, not what you’ve seen
• Much faster than brute force O(n²) approach

Problem 2: Group Anagrams

Difficulty: Medium
Tags: Hash Map, String, Sorting

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An anagram is a word formed by rearranging the letters of another word, using all original letters exactly once.

Example

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

Approach: Sorted String as Key

Anagrams have identical characters when sorted. Use sorted string as the hash map key to group anagrams together.

C# Solution

public class Solution 
{
    public IList<IList<string>> GroupAnagrams(string[] strs) 
    {
        var groups = new Dictionary<string, IList<string>>();
        
        foreach (string str in strs) 
        {
            // Sort characters to create key
            char[] chars = str.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);
            
            // Add to appropriate group
            if (!groups.ContainsKey(key)) 
            {
                groups[key] = new List<string>();
            }
            groups[key].Add(str);
        }
        
        return groups.Values.ToList();
    }
}

Python Solution

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        
        for s in strs:
            # Sort string to create key
            key = tuple(sorted(s))
            groups[key].append(s)
        
        return list(groups.values())

Time Complexity: O(n * k log k) where n is number of strings, k is max string length
Space Complexity: O(n * k)

Alternative: Character Count as Key

For better performance when strings are long:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        
        for s in strs:
            # Count characters (26 lowercase letters)
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            
            # Use tuple of counts as key
            groups[tuple(count)].append(s)
        
        return list(groups.values())

Time Complexity: O(n * k) – better for long strings

Problem 3: Subarray Sum Equals K

Difficulty: Medium
Tags: Hash Map, Prefix Sum, Array

Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: Subarrays [1,1] and [1,1] sum to 2

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: Subarrays [1,2] and [3] sum to 3

Approach: Prefix Sum with Hash Map

Key Insight: If prefixSum[j] - prefixSum[i] = k, then subarray from i+1 to j has sum k.

Rearranging: prefixSum[i] = prefixSum[j] - k

Store prefix sums in hash map and check if currentSum - k exists.

C# Solution

public class Solution 
{
    public int SubarraySum(int[] nums, int k) 
    {
        // Map stores: prefixSum -> frequency
        var prefixSumCount = new Dictionary<int, int>();
        prefixSumCount[0] = 1;  // Empty subarray has sum 0
        
        int currentSum = 0;
        int count = 0;
        
        foreach (int num in nums) 
        {
            currentSum += num;
            
            // Check if (currentSum - k) exists
            // This means there's a subarray with sum k
            if (prefixSumCount.ContainsKey(currentSum - k)) 
            {
                count += prefixSumCount[currentSum - k];
            }
            
            // Add current prefix sum to map
            if (prefixSumCount.ContainsKey(currentSum)) 
            {
                prefixSumCount[currentSum]++;
            } 
            else 
            {
                prefixSumCount[currentSum] = 1;
            }
        }
        
        return count;
    }
}

Python Solution

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # Map stores: prefixSum -> frequency
        prefix_sum_count = defaultdict(int)
        prefix_sum_count[0] = 1  # Empty subarray has sum 0
        
        current_sum = 0
        count = 0
        
        for num in nums:
            current_sum += num
            
            # Check if (current_sum - k) exists
            if (current_sum - k) in prefix_sum_count:
                count += prefix_sum_count[current_sum - k]
            
            # Add current prefix sum to map
            prefix_sum_count[current_sum] += 1
        
        return count

Time Complexity: O(n)
Space Complexity: O(n)

Visual Example

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

Iteration 1: num = 1
  currentSum = 1
  Need: 1 - 3 = -2 (not found)
  Store: {0: 1, 1: 1}

Iteration 2: num = 2
  currentSum = 3
  Need: 3 - 3 = 0 (found! count = 1)
  Subarray [1,2] has sum 3
  Store: {0: 1, 1: 1, 3: 1}

Iteration 3: num = 3
  currentSum = 6
  Need: 6 - 3 = 3 (found! count = 2)
  Subarray [3] has sum 3
  Store: {0: 1, 1: 1, 3: 1, 6: 1}

Result: 2 subarrays

Problem 4: Intersection of Two Arrays

Difficulty: Easy
Tags: Hash Map, Set, Array

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4] or [4,9]

Approach: Set Intersection

Use sets (hash-based) for O(1) lookups and automatic deduplication.

C# Solution

public class Solution 
{
    public int[] Intersection(int[] nums1, int[] nums2) 
    {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        
        set1.IntersectWith(set2);
        
        return set1.ToArray();
    }
}

Python Solution

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

Time Complexity: O(n + m)
Space Complexity: O(n + m)

Problem 5: Unique Email Addresses

Difficulty: Easy
Tags: Hash Map, String

Problem Statement

Given an array of strings emails where we send one email to each emails[i], return the number of different addresses that actually receive mails.

Rules:

• In local name (before @): ignore dots, ignore everything after +
• Domain name: no transformations

Example

Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com"]
Output: 1
Explanation: Both emails forward to "testemail@leetcode.com"

Approach: Normalize and Use Set

Transform each email according to rules, store in set for automatic deduplication.

C# Solution

public class Solution 
{
    public int NumUniqueEmails(string[] emails) 
    {
        var uniqueEmails = new HashSet<string>();
        
        foreach (string email in emails) 
        {
            string[] parts = email.Split('@');
            if (parts.Length != 2) continue;
            
            string localName = parts[0];
            string domainName = parts[1];
            
            // Remove dots
            localName = localName.Replace(".", "");
            
            // Remove everything after +
            int plusIndex = localName.IndexOf('+');
            if (plusIndex != -1) 
            {
                localName = localName.Substring(0, plusIndex);
            }
            
            string normalizedEmail = localName + "@" + domainName;
            uniqueEmails.Add(normalizedEmail);
        }
        
        return uniqueEmails.Count;
    }
}

Python Solution

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        unique_emails = set()
        
        for email in emails:
            if '@' not in email:
                continue
            
            local_name, domain_name = email.split('@')
            
            # Remove dots
            local_name = local_name.replace('.', '')
            
            # Remove everything after +
            if '+' in local_name:
                local_name = local_name.split('+')[0]
            
            normalized_email = local_name + '@' + domain_name
            unique_emails.add(normalized_email)
        
        return len(unique_emails)

Time Complexity: O(n * m) where n is number of emails, m is average email length
Space Complexity: O(n * m)

Problem 6: First Unique Character in a String

Difficulty: Easy
Tags: Hash Map, String, Queue

Problem Statement

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example

Input: s = "leetcode"
Output: 0

Input: s = "loveleetcode"
Output: 2

Input: s = "aabb"
Output: -1

Approach: Two-Pass with Frequency Map

1. First pass: count character frequencies
2. Second pass: find first character with frequency 1

C# Solution

public class Solution 
{
    public int FirstUniqChar(string s) 
    {
        // Count frequencies
        var frequency = new Dictionary<char, int>();
        foreach (char c in s) 
        {
            if (frequency.ContainsKey(c)) 
            {
                frequency[c]++;
            } 
            else 
            {
                frequency[c] = 1;
            }
        }
        
        // Find first unique character
        for (int i = 0; i < s.Length; i++) 
        {
            if (frequency[s[i]] == 1) 
            {
                return i;
            }
        }
        
        return -1;
    }
}

Python Solution

from collections import Counter

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Count frequencies
        frequency = Counter(s)
        
        # Find first unique character
        for i, char in enumerate(s):
            if frequency[char] == 1:
                return i
        
        return -1

Time Complexity: O(n)
Space Complexity: O(1) – at most 26 lowercase letters

Alternative: Single Pass with Order Tracking

from collections import OrderedDict

class Solution:
    def firstUniqChar(self, s: str) -> int:
        char_info = OrderedDict()
        
        for i, char in enumerate(s):
            if char in char_info:
                char_info[char] = -1  # Mark as duplicate
            else:
                char_info[char] = i   # Store first occurrence
        
        for index in char_info.values():
            if index != -1:
                return index
        
        return -1

Key Takeaways

Hash Map Patterns

1. Complement Pattern: Store what you’re looking for (Two Sum)
2. Grouping Pattern: Use transformed value as key (Group Anagrams)
3. Frequency Counter: Count occurrences for analysis
4. Prefix Sum Pattern: Store cumulative sums for subarray problems
5. Normalization Pattern: Transform data before deduplication

Choosing Data Structures

• Dictionary/HashMap: When you need key-value pairs
• HashSet/Set: When you only need to track existence
• defaultdict: When you want automatic default values (Python)
• Counter: Specifically for frequency counting (Python)

Best Practices

• Check if key exists before accessing (avoid KeyError/exceptions)
• Use ContainsKey in C#, in operator in Python
• Consider defaultdict in Python for cleaner code
• Use sets for deduplication and membership testing
• Think about what makes a good key (immutable, hashable)

Common Pitfalls

Watch out for:

• Mutable keys (lists, objects) – use tuples instead
• Hash collisions in custom objects – implement proper GetHashCode/__hash__
• Memory usage with large hash maps
• Not handling edge cases (empty input, duplicates)

When to Use Hash Maps

Perfect for:

• Fast lookups (O(1) average)
• Counting frequencies
• Detecting duplicates
• Caching/memoization
• Grouping related data

Not ideal for:

• When you need ordered traversal (use TreeMap/SortedDictionary)
• When memory is extremely limited
• When keys are sequential integers (consider array)

Practice Problems

Ready to master hash maps? Try these:

1. Longest Substring Without Repeating Characters – Sliding window + hash map
2. Contiguous Array – Prefix sum pattern
3. 4Sum II – Multi-map technique
4. Valid Sudoku – Multiple hash sets
5. LRU Cache – Hash map + doubly linked list

Conclusion

Hash maps are one of the most powerful tools in your algorithmic toolkit. They transform many O(n²) brute force solutions into elegant O(n) algorithms by trading space for time. Mastering hash map patterns—complement finding, frequency counting, prefix sums, and grouping—will dramatically improve your problem-solving capabilities.

The key is recognizing when a problem can benefit from instant lookups and choosing the right hash-based data structure for your needs.

What’s Next? In our next article, we’ll explore trees and graph algorithms, building on our understanding of efficient data access patterns.

Happy coding! 🚀

Have questions or suggestions? Drop a comment below!