Arrays and Hashing in DSA — HashMap Patterns with Examples (Python & Java)

Arrays are the most asked topic in coding interviews, and hashing (hash sets and hash maps) is the tool that turns slow O(n²) array solutions into fast O(n) ones. Learn the four patterns below and a huge share of "easy" and "medium" questions become routine.

Quick refresher: what makes arrays and hash maps fast

Operation	Array	Hash set / hash map
Read by index `arr[i]`	O(1)	—
Search for a value	O(n)	O(1) average
Insert / delete at end	O(1)	O(1) average
Insert / delete in the middle	O(n) (shifting)	O(1) average

A hash map stores key → value pairs. It computes a "hash" of the key to jump straight to where the value lives, so lookups don't scan the whole collection. That's the superpower we'll use again and again.

Python: set(), dict(), collections.Counter, collections.defaultdict
Java: HashSet, HashMap, map.getOrDefault(key, 0)

Pattern 1 — "Have I seen this before?" (hash set)

Use when: the question asks about duplicates, or whether something appeared earlier.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

One pass, O(n) time, O(n) space — versus O(n²) for comparing every pair.

Pattern 2 — Count frequencies (hash map)

Use when: the question mentions anagram, most frequent, majority, count of each.

Example — Valid Anagram: are "listen" and "silent" made of the same letters?

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)   # O(n)

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];             // only lowercase a–z
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}

Tip: when the keys are small and fixed (26 letters), a plain array of counts is faster and simpler than a hash map.

Group Anagrams extends the idea: use the sorted word (or the 26-count tuple) as the map key, and group words with the same key.

Pattern 3 — The complement trick (Two Sum)

Problem: given nums and target, return indices of two numbers that add up to target.

The brute force checks every pair — O(n²). The insight: for each number x, the partner we need is exactly target − x. So as we walk the array, we ask the map whether that partner has already appeared.

def two_sum(nums, target):
    index_of = {}                        # value → index
    for i, x in enumerate(nums):
        need = target - x
        if need in index_of:
            return [index_of[need], i]
        index_of[x] = i                  # store AFTER checking (don't pair x with itself)
    return []

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

Dry run — nums = [2, 7, 11, 15], target = 9:

i	x	need	map before	found?
0	2	7	{}	no → store 2:0
1	7	2	{2:0}	yes → [0, 1]

O(n) time, O(n) space. This "look for the complement" idea appears in dozens of problems.

Pattern 4 — Prefix sums (fast range totals)

Use when: the question asks about sums of subarrays or many range-sum queries.

Build prefix[i] = sum of the first i elements. Then the sum of nums[l..r] is prefix[r+1] − prefix[l] — O(1) per query after O(n) setup.

Subarray Sum Equals K combines prefix sums with Pattern 3: a subarray ending at i sums to k exactly when some earlier prefix equals current_prefix − k.

def subarray_sum(nums, k):
    count, running = 0, 0
    seen = {0: 1}                # prefix sum → how many times we've seen it
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

This works even with negative numbers, where the sliding window technique fails.

Bonus — Kadane's algorithm (Maximum Subarray)

To find the subarray with the largest sum: at each element, either extend the current subarray or start fresh — whichever is bigger.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)    # extend, or restart at x
        best = max(best, cur)
    return best

O(n) time, O(1) space. If the running sum becomes worse than starting over, drop it.

How to recognise the pattern

The question says…	Reach for
duplicate, seen before, unique	hash set
anagram, frequency, most common, majority	hash map / count array
two numbers that sum to… / pair with…	complement lookup in a map
subarray sum, range sum, sum equals k	prefix sum (+ map)
maximum / minimum subarray sum	Kadane's
sorted array + pair/triplet	two pointers (next lesson)

Common mistakes

Using a list for membership checks (x in list is O(n)). Use a set.
In Two Sum, storing the number before checking — then x + x = target pairs an element with itself.
Forgetting seen = {0: 1} in prefix-sum counting — you miss subarrays that start at index 0.
Sorting when the question needs the original indices — sorting destroys them.

Key takeaways

Hashing gives O(1) average lookups; use it to remove inner loops.
Four patterns: seen-set, frequency map, complement lookup, prefix sums.
Always state the trade-off: O(n) time because we spend O(n) extra space.

Practise with the problems below, then take the quiz to lock it in.

Arrays & Hashing — The Patterns Behind Most Interview Questions