DSA Patterns: Hashing

If there’s one pattern that’s pure gold in interviews, it’s Hashing. Actually, it is more of a utility approach that helps build the foundations of a lot of optimized solutions. Hashing, from a Java perspective, means the use of HashMap and HashSet.

Using HashMap or HashSet, we unlock O(1) time access to check frequency, presence, or retrieve associated data. It’s the backbone of countless problems across arrays, strings, trees, and graphs.

---

📌 When to Use Hashing

Reach for this pattern when you spot:

• “Find duplicates”
• “Check if something exists”
• “Count frequency of items”
• “Group elements by a rule (e.g., anagrams)”
• “Track seen states or combinations”
• “Constant-time lookup needed”

---

🔍 Core Idea

Use a HashMap or HashSet to store values you've seen before, so you don’t have to search for them again.

• HashMap: key -> value mappings (e.g., char -> count, num -> index)
• HashSet: Only tracks existence (has this been seen before?)

This turns brute-force O(n²) ideas into sleek O(n) solutions.

---

⚒️ Common Use Cases

---

🧰 Code Template(s)

Count Frequencies (HashMap)

Map<Character, Integer> map = new HashMap<>(); // create a map to store frequency of each character 
for (char c : str.toCharArray()) {             // iterate through each character in the string 
    map.put(c, map.getOrDefault(c, 0) + 1);     // increment count or insert 1 if not already present 
}

Check for Seen Items (HashSet)

Set<Integer> seen = new HashSet<>();           // create a set to track seen numbers 
for (int num : nums) {                         // iterate through each number in array 
    if (seen.contains(num)) return true;        // if number already in set, duplicate found 
    seen.add(num);                              // otherwise, add number to set 
}

---

🔎 Mini Case Studies: Hashing in Action

1. Two Sum (Leetcode #1)

🧠 Problem: Find indices of two numbers in an array that sum to a target.

❌ Without Hashing (Brute Force): Check all pairs using nested loops — O(n²) time.

for (int i = 0; i < nums.length; i++) { 
    for (int j = i + 1; j < nums.length; j++) { 
        if (nums[i] + nums[j] == target) 
            return new int[]{i, j}; 
    } 
}

Pain Point: You redundantly search the rest of the array for each element.

✅ With Hashing (Optimized): Use HashMap to store previously seen numbers. Lookup complement in O(1).

Map<Integer, Integer> map = new HashMap<>(); 
for (int i = 0; i < nums.length; i++) { 
    int diff = target - nums[i]; 
    if (map.containsKey(diff)) 
        return new int[]{map.get(diff), i}; 
    map.put(nums[i], i); 
}

Key Insight: Hashing turns searching into instant lookup. Instead of “scan the rest,” ask “have I seen its complement?”

---

2. Valid Anagram (Leetcode #242)

🧠 Problem: Check if two strings are anagrams (same letters, same frequency).

❌ Without Hashing (Naive): Sort both strings and compare. Sorting = O(n log n) time.

char[] sArr = s.toCharArray(); 
char[] tArr = t.toCharArray(); 
Arrays.sort(sArr); 
Arrays.sort(tArr); 
return Arrays.equals(sArr, tArr);

Pain Point: Sorting works, but it’s slower and adds unnecessary overhead.

✅ With Hashing (Optimized): Count frequency in one string, subtract in the other.

Map<Character, Integer> map = new HashMap<>(); 
for (char c : s.toCharArray()) 
    map.put(c, map.getOrDefault(c, 0) + 1); 

for (char c : t.toCharArray()) { 
    if (!map.containsKey(c)) return false; 
    map.put(c, map.get(c) - 1); 
    if (map.get(c) == 0) map.remove(c); 
} 
return map.isEmpty();

Key Insight: You don’t need to sort. Just record and cancel out frequencies. HashMap helps verify character balance directly in O(n) time (where n = max(len(s), len(t)).

3. Contains Duplicate (Leetcode #217)

🧠 Problem: Check if any number appears more than once.

❌ Without Hashing (Brute Force): Compare each pair using two loops — O(n²) time.

for (int i = 0; i < nums.length; i++) { 
    for (int j = i + 1; j < nums.length; j++) { 
        if (nums[i] == nums[j]) return true; 
    } 
} 
return false;

Pain Point: You redundantly check every pair and don’t remember anything.

✅ With Hashing (Optimized using HashSet): Track seen numbers with a Set for instant lookup.

Set<Integer> seen = new HashSet<>(); 
for (int num : nums) { 
    if (seen.contains(num)) return true; 
    seen.add(num); 
} 
return false;

Key Insight: HashSet turns this into a memory check. Instead of scanning backward, you simply ask “Have I seen this already?” in O(1) time.

---

⚠️ Pitfalls to Watch

• Always choose the right key. For grouping, sort the string or build a custom signature.
• Don’t forget to remove from HashSet if you're sliding a window.
• Use .getOrDefault() or check map.containsKey() to avoid null.
• HashMap’s key needs proper equals() and hashCode() if you're using custom objects.

---

✅ LeetCode Problems to Practice (Hashing)

---

💡 Final Tip

Hashing isn’t the full strategy — it’s a powerful sidekick.

Use it to speed up lookups, track frequency, or eliminate duplicates — and it’ll help you unlock clean and efficient solutions in many patterns.