CodeMosa

Master LeetCode Patterns

BeginnerArrays & StringsRead Arrays & Strings Fundamentals →

Hash Map / Hash Table

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

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

What is Hash Map / Hash Table?

#
Definition: Use O(1) average-time key→value lookups for counting, complement searches, deduping, and grouping.

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.

How Hash Map / Hash Table works

#

Frequency maps, complement lookups for pair problems, and index maps for last-seen positions or window constraints.

  • Need to find pairs, complements, or matching elements
  • Counting frequencies or occurrences
  • Detecting duplicates or unique elements

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

Code Templates

#
Frequency maps, complement lookups for pair problems, and index maps for last-seen positions or window constraints.
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

Pattern Variants & Approaches

#
Different methodologies and implementations for this pattern
1

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
2

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
3

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

Related Patterns

#
Prefix/Suffix ArraysSliding WindowTwo Pointers

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