3. Hashing

What Interviewers Test Here

• Recognising when $O(n^2)$ can be reduced to $O(n)$ using a hash map
• Frequency counting with Counter and defaultdict
• Two-sum variants (complement lookup pattern)
• Grouping / deduplication

from collections import Counter, defaultdict

# --- Two Sum (classic) ---
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}    # value → index
    for i, x in enumerate(nums):
        comp = target - x
        if comp in seen:
            return [seen[comp], i]
        seen[x] = i
    return []

# --- Subarray sum equals k ---
def subarray_sum(nums: list[int], k: int) -> int:
    count = prefix = 0
    freq  = defaultdict(int)
    freq[0] = 1    # empty prefix sums to 0
    for x in nums:
        prefix += x
        count += freq[prefix - k]
        freq[prefix] += 1
    return count

# --- Longest consecutive sequence --- O(n)
def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for n in num_set:
        if n - 1 not in num_set:   # only start counting from sequence starts
            cur, length = n, 1
            while cur + 1 in num_set:
                cur += 1; length += 1
            best = max(best, length)
    return best

---

Conceptual Q&A

Q1: "Given a list of strings, group all anagrams together."

Walkthrough:

"Two strings are anagrams if they contain the same characters in the same frequencies. I need a key that two anagrams share but non-anagrams don't.

Option 1: Sort each string — 'eat' and 'tea' both become 'aet'. Use this as the dict key. $O(n \cdot L \log L)$ where $L$ = avg word length.

Option 2: Use a frequency tuple of 26 character counts as the key. $O(n \cdot L)$ — faster but more verbose.

I'll go with sorted string — cleaner and interview-friendly."

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[tuple, list] = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))   # e.g. "eat" → ('a','e','t')
        groups[key].append(s)
    return list(groups.values())

# Test: ["eat","tea","tan","ate","nat","bat"]
# → [["eat","tea","ate"], ["tan","nat"], ["bat"]]

---

Q2: "Find the first non-repeating character in a string."

Walkthrough:

"I need to know the frequency of each character (hash map), then find the first one with frequency 1. Two passes: first pass to build frequencies, second pass through the string (in order) to find the first with count 1. $O(n)$ time, $O(1)$ space (at most 26 characters in alphabet)."

def first_unique_char(s: str) -> int:
    freq = Counter(s)
    for i, c in enumerate(s):
        if freq[c] == 1:
            return i
    return -1

print(first_unique_char("leetcode"))   # 0 ('l')
print(first_unique_char("aabb"))       # -1

---

Q3: "Given an array, find the number of subarrays whose sum equals k."

Walkthrough:

"Brute force: try every (i, j) pair — $O(n^2)$.

Optimise: I'll use prefix sums + hash map. Let prefix[i] = sum of nums[0..i-1]. A subarray nums[l..r] has sum = prefix[r+1] - prefix[l]. I want this to equal k, so I want prefix[l] = prefix[r+1] - k.

As I compute prefix sums left to right, I keep a hash map of how many times each prefix sum has appeared. At each position, I add freq[prefix - k] to the count. $O(n)$ time and space."

def count_subarrays_sum_k(nums: list[int], k: int) -> int:
    count = prefix = 0
    freq = defaultdict(int)
    freq[0] = 1       # one way to get prefix sum of 0: take nothing
    for x in nums:
        prefix += x
        count  += freq[prefix - k]   # how many prior prefixes let us form sum k
        freq[prefix] += 1
    return count

---