🗂

Frequency HashMap

Trade O(1) average-case lookups for extra space. Count occurrences with a frequency map, or store previously seen values to answer "have I seen this before?" in O(1) per query.

Array String HashMap Time O(n) Space O(n)

📋 When to Use

Count occurrences of elements (frequency map)
Check if a complement / pair was seen earlier (Two Sum style)
Detect duplicates or find missing elements
Group elements by a derived key (anagram grouping)
Find elements appearing more than n/k times (majority)

💡 Brute-force nested loops run O(n²). A HashMap turns the inner scan into a single O(1) lookup — shrinking the whole algorithm to O(n).

⚡ Complexity

Time

O(n)

Space

O(n)

Single pass through the array — each element is inserted and looked up at most once. Extra O(n) space for the map, where n is the number of distinct keys stored.

Problem Given an integer array nums and a target, return the indices of the two numbers that add up to target. At each index i, check if target − nums[i] already exists in seen. If yes → found! If no → store nums[i] → i.
Input: nums = [2, 5, 8, 1, 4, 7], target = 11 · Answer: [4, 5] (4 + 7 = 11)

Step 1 / —

🔍 Check Complement

➕ Add to Map

✅ Found!

✅ Done

nums = [2, 5, 8, 1, 4, 7] target = 11

seen (HashMap)

{ }

—

i = —

nums[i] = —

need = —

Click ▶ Play or Next ▶ to start

Map<Integer, Integer> seen = new HashMap<>();

Java Pattern SkeletonJAVA

// ── 1. Frequency map — count occurrences ────────────────────────
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums)
    freq.merge(n, 1, Integer::sum);   // freq[n]++

// ── 2. Existence / Two Sum style — seen map ──────────────────────
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (seen.containsKey(complement))
        return new int[]{ seen.get(complement), i };   // found pair
    seen.put(nums[i], i);   // store value → index
}

🎯 Practice Problems

#1Two SumEasy #217Contains DuplicateEasy #383Ransom NoteEasy #169Majority ElementEasy #49Group AnagramsMedium #128Longest Consecutive SequenceMedium #560Subarray Sum Equals KMedium #41First Missing PositiveHard