​

Array & Hashing

​

Key Patterns & Techniques

​

1. Hash Map for O(1) Lookups

• Store elements for constant-time access
• Track seen elements or complements
• Map elements to indices or frequencies

​

2. Frequency Counting

• Use Counter or hash map to count occurrences
• Group elements by properties
• Find duplicates or unique elements

​

3. Prefix Sum

• Precompute cumulative sums for range queries
• Use with hash map for subarray problems
• Space-time tradeoff for multiple queries

​

4. Sorting + Hash Map

• Sort for grouping similar elements
• Use hash map for quick lookups after sorting
• Interval problems often require sorting first

​

Common Approaches

​

Two Sum Pattern

def twoSum(nums: List[int], target: int) -> List[int]:
    """
    Find two numbers that add up to target using hash map.
    Time: O(n), Space: O(n)
    """
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

​

Frequency Counting Pattern

from collections import Counter

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    """
    Group strings by character frequency.
    Time: O(n * k), Space: O(n * k)
    """
    groups = {}
    for s in strs:
        # Sort or count chars as key
        key = ''.join(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    return list(groups.values())

​

Prefix Sum Pattern

def subarraySum(nums: List[int], k: int) -> int:
    """
    Count subarrays with sum equal to k.
    Time: O(n), Space: O(n)
    """
    count = 0
    prefix_sum = 0
    sum_freq = {0: 1}  # prefix_sum -> frequency
    
    for num in nums:
        prefix_sum += num
        # Check if (prefix_sum - k) exists
        if prefix_sum - k in sum_freq:
            count += sum_freq[prefix_sum - k]
        sum_freq[prefix_sum] = sum_freq.get(prefix_sum, 0) + 1
    
    return count

​

Problems in This Category

​

Complexity Characteristics

​

Interview Tips

​

Pattern Recognition

• “Find two elements that…” → Hash map for O(n) solution
• “Count frequency/occurrences” → Counter or hash map
• “Subarray sum equals k” → Prefix sum with hash map
• “Group by property” → Hash map with computed keys
• “Merge overlapping…” → Sort first, then single pass

​

Common Mistakes

• Forgetting to handle duplicates in hash map
• Not initializing prefix sum hash with {0: 1}
• Modifying array while iterating over it
• Using list instead of hash set for O(1) lookups
• Not sorting intervals before merging

​

Optimization Strategies

1. Use hash set instead of hash map when only checking existence
2. Counter from collections is cleaner than manual dict updates
3. Prefix sum trades space for time in range queries
4. Sort first when dealing with intervals or grouping
5. Single pass is often possible with the right hash map structure

​

Advanced Patterns

​

Rolling Hash

• For substring matching problems
• Rabin-Karp algorithm
• Time: O(n), Space: O(1)

​

Multi-level Hashing

• Nested hash maps for 2D problems
• Group by multiple properties
• Time: O(n), Space: O(n)

​

Index Mapping

• Map values to indices for O(1) updates
• Used in problems like “First Missing Positive”
• In-place modifications using array indices as hash