Hashing Interview Problems

Master four essential hashing interview problems — Two Sum, Group Anagrams, Longest Consecutive Sequence, and Subarray with Given Sum using hash maps for O(n) solutions.

Problem 1: Two Sum

Statement: Given an array of integers and a target sum, find two numbers that add up to the target. Return their indices.

Brute Force vs Hash Map

The naive approach checks all pairs — O(n²). With a hash map, for each element nums[i], we check if target - nums[i] already exists in our map. Single pass, O(n).

Key Insight

As we iterate, we build a lookup of "what we have seen so far." For each new number, we ask: "Does the complement exist in what I have already seen?"

Implementation

Example

def two_sum(nums, target): seen = {} # value → index for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return [] # no solution # Example print(two_sum([2, 7, 11, 15], 9)) # [0, 1] → 2 + 7 = 9 print(two_sum([3, 2, 4], 6)) # [1, 2] → 2 + 4 = 6 print(two_sum([3, 3], 6)) # [0, 1] → 3 + 3 = 6

Dry Run

Example

nums = [2, 7, 11, 15], target = 9 i=0: num=2, complement=7, seen={} → 7 not in seen. Add {2:0} i=1: num=7, complement=2, seen={2:0} → 2 IS in seen! Return [0, 1] ✓

Complexity: Time O(n), Space O(n).

Variations: 3Sum (sort + two pointers or hash), 4Sum, Two Sum with sorted array (two pointers, no hash needed).

Problem 3: Longest Consecutive Sequence

Statement: Given an unsorted array of integers, find the length of the longest consecutive elements sequence (e.g., [1,2,3,4] has length 4). Must run in O(n) time.

Key Insight

Put all numbers in a hash set for O(1) lookup. For each number that is a sequence start (i.e., num - 1 is not in the set), count how far the sequence extends forward.

The critical optimization: only start counting from sequence beginnings. This ensures each element is visited at most twice total — O(n).

Implementation

Example

def longest_consecutive(nums): if not nums: return 0 num_set = set(nums) max_length = 0 for num in num_set: # Only start counting if num is the START of a sequence if num - 1 not in num_set: current = num length = 1 while current + 1 in num_set: current += 1 length += 1 max_length = max(max_length, length) return max_length # Examples print(longest_consecutive([100, 4, 200, 1, 3, 2])) # 4 (sequence: 1,2,3,4) print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])) # 9 (0-8)

Dry Run

Check 100: Is 99 in set? No	start here. 101 in set? No. Length = 1.
Check 4: Is 3 in set? Yes	NOT a start. Skip.
Check 200: Is 199 in set? No	start here. 201 in set? No. Length = 1.
Check 1: Is 0 in set? No	start here. 2? Yes. 3? Yes. 4? Yes. 5? No. Length = 4.
Check 3: Is 2 in set? Yes	skip.
Check 2: Is 1 in set? Yes	skip.

Complexity: Time O(n) — each element is the start of at most one sequence, and each element is visited at most twice. Space O(n) for the set.

Problem 4: Subarray with Given Sum

Statement: Given an array of integers (may include negatives), find if there exists a contiguous subarray that sums to a given value k. Alternatively, count the number of such subarrays.

Key Insight (Prefix Sum + Hash Map)

If prefix_sum[j] - prefix_sum[i] = k, then the subarray from index i+1 to j has sum k. Rearranging: prefix_sum[j] - k = prefix_sum[i]. For each position j, we need to know how many earlier positions i have prefix_sum[i] = prefix_sum[j] - k.

Store prefix sum frequencies in a hash map. This converts a subarray sum problem into a hash lookup problem.

Implementation

Example

def subarray_sum_count(nums, k): """Count the number of subarrays with sum equal to k.""" count = 0 prefix_sum = 0 # Map: prefix_sum_value → number of times this prefix sum has occurred prefix_map = {0: 1} # empty prefix has sum 0 (occurs once) for num in nums: prefix_sum += num # How many earlier prefixes had sum = prefix_sum - k? if prefix_sum - k in prefix_map: count += prefix_map[prefix_sum - k] # Record current prefix sum prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count # Examples print(subarray_sum_count([1, 1, 1], 2)) # 2: [1,1] at pos 0-1 and 1-2 print(subarray_sum_count([1, 2, 3], 3)) # 2: [1,2] and [3] print(subarray_sum_count([1, -1, 0], 0)) # 3: [1,-1], [-1,0], [1,-1,0]

Boolean version (does any such subarray exist?)

python example

def has_subarray_sum(nums, k):
    """Return True if any contiguous subarray sums to k."""
    prefix_sum = 0
    seen_sums = {0}
    
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in seen_sums:
            return True
        seen_sums.add(prefix_sum)
    
    return False

Dry Run

prefix_sum = 0, prefix_map = {0	1}
i=0	prefix_sum = 1. Check 1-3 = -2 in map? No. Map = {0:1, 1:1}
i=1	prefix_sum = 3. Check 3-3 = 0 in map? YES (count 1)! Count=1. Map = {0:1, 1:1, 3:1}
i=2	prefix_sum = 6. Check 6-3 = 3 in map? YES (count 1)! Count=2. Map = {0:1, 1:1, 3:1, 6:1}
Result: 2 subarrays	[1,2] (sum=3) and [3] (sum=3)

Complexity: Time O(n), Space O(n).

Summary Table

Problem	Hash Map Role	Time	Space	Key Technique
Two Sum	Complement lookup	O(n)	O(n)	Store seen values, check complement
Group Anagrams	Frequency-based grouping	O(n×k)	O(n×k)	Canonical form as hash key
Longest Consecutive	Set membership test	O(n)	O(n)	Only start from sequence beginnings
Subarray Sum	Prefix sum frequency	O(n)	O(n)	prefix[j] - prefix[i] = k

All four problems share a common theme: transform an O(n²) brute-force approach into O(n) by trading space for time via hash-based lookup. This pattern — "have I seen the value I need?" — is the single most powerful hashing technique in interviews.

Problem 1: Two Sum

Statement: Given an array of integers and a target sum, find two numbers that add up to the target. Return their indices.

Brute Force vs Hash Map

The naive approach checks all pairs — O(n²). With a hash map, for each element nums[i], we check if target - nums[i] already exists in our map. Single pass, O(n).

Key Insight

As we iterate, we build a lookup of "what we have seen so far." For each new number, we ask: "Does the complement exist in what I have already seen?"

Implementation

Example

Dry Run

Example

nums = [2, 7, 11, 15], target = 9 i=0: num=2, complement=7, seen={} → 7 not in seen. Add {2:0} i=1: num=7, complement=2, seen={2:0} → 2 IS in seen! Return [0, 1] ✓

Complexity: Time O(n), Space O(n).

Variations: 3Sum (sort + two pointers or hash), 4Sum, Two Sum with sorted array (two pointers, no hash needed).

Problem 3: Longest Consecutive Sequence

Statement: Given an unsorted array of integers, find the length of the longest consecutive elements sequence (e.g., [1,2,3,4] has length 4). Must run in O(n) time.

Key Insight

Put all numbers in a hash set for O(1) lookup. For each number that is a sequence start (i.e., num - 1 is not in the set), count how far the sequence extends forward.

The critical optimization: only start counting from sequence beginnings. This ensures each element is visited at most twice total — O(n).

Implementation

Example

Dry Run

Check 100: Is 99 in set? No	start here. 101 in set? No. Length = 1.
Check 4: Is 3 in set? Yes	NOT a start. Skip.
Check 200: Is 199 in set? No	start here. 201 in set? No. Length = 1.
Check 1: Is 0 in set? No	start here. 2? Yes. 3? Yes. 4? Yes. 5? No. Length = 4.
Check 3: Is 2 in set? Yes	skip.
Check 2: Is 1 in set? Yes	skip.

Complexity: Time O(n) — each element is the start of at most one sequence, and each element is visited at most twice. Space O(n) for the set.

Problem 4: Subarray with Given Sum

Statement: Given an array of integers (may include negatives), find if there exists a contiguous subarray that sums to a given value k. Alternatively, count the number of such subarrays.

Key Insight (Prefix Sum + Hash Map)

Store prefix sum frequencies in a hash map. This converts a subarray sum problem into a hash lookup problem.

Implementation

Example

Boolean version (does any such subarray exist?)

python example

def has_subarray_sum(nums, k):
    """Return True if any contiguous subarray sums to k."""
    prefix_sum = 0
    seen_sums = {0}
    
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in seen_sums:
            return True
        seen_sums.add(prefix_sum)
    
    return False

Dry Run

prefix_sum = 0, prefix_map = {0	1}
i=0	prefix_sum = 1. Check 1-3 = -2 in map? No. Map = {0:1, 1:1}
i=1	prefix_sum = 3. Check 3-3 = 0 in map? YES (count 1)! Count=1. Map = {0:1, 1:1, 3:1}
i=2	prefix_sum = 6. Check 6-3 = 3 in map? YES (count 1)! Count=2. Map = {0:1, 1:1, 3:1, 6:1}
Result: 2 subarrays	[1,2] (sum=3) and [3] (sum=3)

Complexity: Time O(n), Space O(n).

Summary Table

Problem	Hash Map Role	Time	Space	Key Technique
Two Sum	Complement lookup	O(n)	O(n)	Store seen values, check complement
Group Anagrams	Frequency-based grouping	O(n×k)	O(n×k)	Canonical form as hash key
Longest Consecutive	Set membership test	O(n)	O(n)	Only start from sequence beginnings
Subarray Sum	Prefix sum frequency	O(n)	O(n)	prefix[j] - prefix[i] = k

Hashing Interview Problems

Problem 1: Two Sum

Brute Force vs Hash Map

Key Insight

Implementation

Dry Run

Problem 3: Longest Consecutive Sequence

Key Insight

Implementation

Dry Run

Problem 4: Subarray with Given Sum

Key Insight (Prefix Sum + Hash Map)

Implementation

Boolean version (does any such subarray exist?)

Dry Run

Summary Table

Continue learning this concept

Hashing Interview Problems

Problem 1: Two Sum

Brute Force vs Hash Map

Key Insight

Implementation

Dry Run

Problem 3: Longest Consecutive Sequence

Key Insight

Implementation

Dry Run

Problem 4: Subarray with Given Sum

Key Insight (Prefix Sum + Hash Map)

Implementation

Boolean version (does any such subarray exist?)

Dry Run

Summary Table

Continue learning this concept