BeginnerArrays & Strings

Hash Map / Hash Table

Use hash maps for O(1) lookups to solve frequency counting and pairing problems

Time: O(n)

Space: O(n)

Pattern Overview

Core Idea

Hash maps provide O(1) average-case lookup, insertion, and deletion. They're essential for tracking frequencies, finding complements, detecting duplicates, and mapping relationships between elements.

When to Use

Use when you need fast lookups, counting element frequencies, finding pairs with specific relationships, detecting duplicates, or mapping keys to values. Particularly useful for two-sum variants and anagram problems.

General Recognition Cues

General indicators that this pattern might be applicable

Need to find pairs, complements, or matching elements
Counting frequencies or occurrences
Detecting duplicates or unique elements
Anagram or character frequency problems
Need O(1) lookup time
Mapping relationships between elements

Pattern Variants & Approaches

Different methodologies and implementations for this pattern

Frequency Counter

Count occurrences of elements to solve frequency-based problems

When to Use This Variant

Count character/element frequencies
Find most/least frequent elements
Anagram detection
Character replacement problems
Frequency-based validation

Use Case

Anagrams, character frequency, most common elements

Advantages

O(1) increment and lookup
Simple to implement
Works with any hashable type
Natural for counting problems

Implementation

def frequency_counter(s):
      freq = {}
      for char in s:
          freq[char] = freq.get(char, 0) + 1
      return freq
  
  # Example: Valid Anagram
  def is_anagram(s, t):
      if len(s) != len(t):
          return False
      
      freq = {}
      for char in s:
          freq[char] = freq.get(char, 0) + 1
      
      for char in t:
          if char not in freq or freq[char] == 0:
              return False
          freq[char] -= 1
      
      return True

Complement Lookup

Find pairs by looking up complements in O(1) time

When to Use This Variant

Two Sum and variants
Finding pairs with target sum/difference
Complement-based matching
Pair detection problems
Need to check if complement exists

Use Case

Two Sum, pair finding, complement matching

Advantages

Reduces O(n²) to O(n)
Single pass solution possible
Handles duplicates naturally
Flexible for various pair problems

Implementation

def two_sum(nums, target):
      seen = {}
      
      for i, num in enumerate(nums):
          complement = target - num
          
          if complement in seen:
              return [seen[complement], i]
          
          seen[num] = i
      
      return []
  
  # Example: Four Sum Count
  def four_sum_count(A, B, C, D):
      sum_ab = {}
      
      # Store all possible sums from A and B
      for a in A:
          for b in B:
              sum_ab[a + b] = sum_ab.get(a + b, 0) + 1
      
      count = 0
      # Check complements from C and D
      for c in C:
          for d in D:
              complement = -(c + d)
              count += sum_ab.get(complement, 0)
      
      return count

Index Mapping

Map elements to their indices or positions for quick lookups

When to Use This Variant

Need to track element positions
Find indices of elements
Mapping values to locations
Quick position lookup required
Tracking last seen positions

Use Case

Finding indices, position tracking, duplicate detection

Advantages

O(1) position lookup
Tracks multiple occurrences
Useful for index-based problems
Handles updates efficiently

Implementation

def index_mapping(nums):
      index_map = {}
      for i, num in enumerate(nums):
          if num not in index_map:
              index_map[num] = []
          index_map[num].append(i)
      return index_map
  
  # Example: Contains Duplicate II
  def contains_nearby_duplicate(nums, k):
      index_map = {}
      
      for i, num in enumerate(nums):
          if num in index_map and i - index_map[num] <= k:
              return True
          index_map[num] = i
      
      return False

Common Pitfalls

Watch out for these common mistakes

Not handling hash collisions properly
Forgetting to check if key exists before accessing
Using mutable objects as keys (in some languages)
Not considering space complexity (O(n) for hash map)
Incorrect frequency counting logic

Code Templates

Compare implementations across different languages

def hash_map_template(arr):
      hash_map = {}
      
      for i, val in enumerate(arr):
          # Frequency counting
          hash_map[val] = hash_map.get(val, 0) + 1
          
          # Or complement lookup
          complement = target - val
          if complement in hash_map:
              return [hash_map[complement], i]
          
          # Or index mapping
          hash_map[val] = i
      
      return hash_map

Example Problems

Classic LeetCode problems using this pattern

Complexity Analysis

Time Complexity

O(n)

Single pass through array with O(1) hash map operations.

Space Complexity

O(n)

Hash map stores up to n elements in worst case.

Ready to test your knowledge?

Test your pattern recognition with interactive questions