Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 225 ยท Hashing

Hashing Patterns

Solve classic interview problems with hash maps and sets in Python: duplicates, two sum, group anagrams, longest consecutive sequence, subarray sum k, first unique character.

A hash table gives you something that sounds small but changes everything: O(1) memory of the past. While scanning an array you can ask "have I seen this value before?", "where did I see it?" or "how many times?" instantly. Problems that look like they need a nested loop (compare every element with every other) often collapse to a single pass once you store what you have seen.

This lesson teaches the recurring hashing patterns through six classic problems, followed by three more at the end (k-sum, recurring decimals and zero-sum subarrays). Each one starts with the brute force so you can see exactly what the hash table buys you. Make sure you are comfortable with dictionaries and sets first.

The core idea

Almost every hashing solution is one of these four shapes:

TEXT
1. Seen-set        "Have I met this before?"             set of values
2. Value -> index  "Where did I see the partner value?"  dict value -> position
3. Key -> group    "Which items belong together?"        dict canonical-key -> list
4. Prefix -> count "How many earlier prefixes match?"    dict prefix-sum -> count

The trick is deciding what to store as the key. Often it is the value you are looking for ("the number that would complete the pair"), or a canonical form that makes equal things look identical (a sorted word, a tuple of counts).

Pattern 1: duplicates with a seen-set

Problem. Does a list contain any duplicate?

Brute force. Compare every pair: O(nยฒ) time, O(1) space. Sorting. Sort, then compare neighbors: O(n log n) time, O(1) extra space if you sort in place. Hashing. Walk once; stop at the first value already in a set: O(n) time, O(n) space.

Python Contains duplicate: three approaches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 100 distinct numbers, brute force examines 4,950 pairs (100 ร— 99 / 2) while the set solution does 100 steps.

A common follow-up: "duplicate within distance k". Replace the set with a dict value -> last index and check i - last[x] <= k.

Pattern 2: Two Sum (value to index)

Problem. Given nums and a target, return the indexes of two different items that add up to target. (If the list were sorted you could use two pointers; here it is not.)

Brute force. Try every pair: O(nยฒ).

Better. For each x, the partner we need is target - x. Keep a dict from value to index of everything seen so far. If the partner is already there, we are done. Otherwise store x.

TEXT
nums = [3, 8, 5, 11], target = 13
 x=3  need 10 -> not seen            seen = {3:0}
 x=8  need  5 -> not seen            seen = {3:0, 8:1}
 x=5  need  8 -> seen at index 1!    answer (1, 2)

Checking before inserting prevents pairing an element with itself.

Python Two Sum with a dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n). The trade is the standard one: spend memory to save time.

Pattern 3: grouping by a canonical key (Group Anagrams)

Problem. Group words that are anagrams of each other.

Anagrams are words with the same letters. We need a key that is identical for all anagrams and different for non-anagrams. Two options:

  • Sorted word: "tea" and "eat" both become "aet". Cost O(k log k) per word of length k.
  • Letter-count tuple: a tuple of 26 counts. Cost O(k) per word, no sorting. Tuples are hashable; lists are not.
Python Group anagrams

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With n words of maximum length k, the sorted-key version is O(n ยท k log k) and the count version is O(n ยท k). Dictionaries keep first-seen order, so groups come out in a predictable order.

Pattern 4: sets as a fast "is it there?" (Longest Consecutive Sequence)

Problem. Given an unsorted list, find the length of the longest run of consecutive integers (like 100, 4, 200, 1, 3, 2 has 1, 2, 3, 4, length 4). Duplicates and order do not matter. Target: O(n).

Sort-based. Sort and scan: O(n log n). Good, but not O(n).

Hash-based. Put everything in a set. A run starts at a number whose predecessor is not in the set. From each start, count upward while x + 1 is in the set. Because only run starts do the counting, each number is visited a constant number of times overall.

TEXT
set = {100, 4, 200, 1, 3, 2}
100: 99 not in set  -> start, 101 missing -> length 1
4  : 3 in set       -> not a start, skip
200: 199 not in set -> start, length 1
1  : 0 not in set   -> start: 1,2,3,4 -> length 4
Python Longest consecutive sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The inner while looks like a nested loop, but it only runs from run starts, and every number belongs to exactly one run, so the total extra work is at most n. Time O(n), space O(n). If you skipped the x - 1 in values check, a run of length n would be re-walked from each of its members: O(nยฒ).

Pattern 5: prefix sums in a dict (Subarray Sum Equals K)

Problem. Count the contiguous subarrays whose sum is exactly k. The list may contain negative numbers, so sliding window does not work.

Brute force. Try every start and end: O(nยฒ) with a running sum, O(nยณ) if you re-sum each time.

Better. Let prefix[i] be the sum of the first i items (see prefix sums). The subarray from position j to i has sum prefix[i] - prefix[j]. We want this to equal k, so for each i we need the number of earlier prefixes equal to prefix[i] - k. A dict prefix value -> how many times seen answers that in O(1).

TEXT
nums = [1, 2, 3, -3, 3],  k = 3
step  x   running  need (running - k)  earlier prefixes that match   total
 1    1      1          -2                  none                        0
 2    2      3           0                  {0}  (1 time)                1
 3    3      6           3                  {3}  (1 time)                2
 4   -3      3           0                  {0}  (1 time)                3
 5    3      6           3                  {3}  (2 times)               5
Python Subarray sum equals k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The initial {0: 1} is essential: it lets a subarray that starts at index 0 be counted (its prefix minus the empty prefix). Time O(n), space O(n). The same trick finds the longest subarray with sum k if you store the first index of each prefix instead of a count.

Pattern 6: frequency table (First Non-Repeating Character)

Problem. Return the index of the first character that appears exactly once in a string, or -1.

Brute force. For each character, scan the whole string for another copy: O(nยฒ).

Better. Two passes. First count every character, then find the first whose count is 1. Time O(n), space O(1) for a fixed alphabet (O(ฯƒ) in general, where ฯƒ is the alphabet size).

Python First unique character

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that s.count(ch) inside a loop is the sneaky O(nยฒ): each call scans the string.

Pattern 7: the k-sum family (4Sum)

Problem. Find all unique quadruplets in an array that add up to a target.

Idea. Two Sum is the base case (hash map, or two pointers on sorted data). 3Sum is "fix one number, solve Two Sum for the rest", and 4Sum is "fix two numbers, solve Two Sum for the rest". Sorting first makes duplicate handling easy: skip a value if it equals the previous one at the same loop level.

k Method Time
2 hash map or sorted two pointers O(n)
3 fix one, then 2-sum O(nยฒ)
4 fix two, then 2-sum O(nยณ)

A faster 4Sum for counting problems stores all pair sums in a dictionary, the meet in the middle idea: split into two halves and combine, O(nยฒ) time and space.

Python 4Sum with sorting and two pointers, plus the pair-sum trick

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pattern 8: remainders in a dict (Fraction to Decimal)

Problem. Write the fraction numerator / denominator as a decimal string. If the decimals repeat, put the repeating part in parentheses: 1/3 is 0.(3), 2/3 is 0.(6), 1/6 is 0.1(6).

Idea. Do long division. At each step the next digit depends only on the current remainder. If a remainder appears for the second time, the digits from its first appearance onward will repeat forever. A dict remainder -> position in the output finds the start of the cycle in O(1) per step. The remainder is always below the denominator, so the loop ends after at most denominator steps.

Python Fraction to recurring decimal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same "state seen before means a cycle" trick finds loops in a linked list or in a sequence such as "sum of squares of digits" (happy numbers).

Pattern 9: zero-sum subarrays

This is pattern 5 (prefix sums in a dict) with k = 0. Two equal prefix sums mean the elements between them add up to zero. Three questions share the same loop:

  • Does a zero-sum subarray exist? Return as soon as a prefix sum is seen twice, or equals 0 itself.
  • Longest zero-sum subarray? Store the first index of each prefix sum; the answer is the largest i - first[prefix].
  • How many zero-sum subarrays? Count each prefix sum; every pair of equal prefix sums is one subarray.
Python Zero-sum subarrays: exists, longest, count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

An O(1) insert, delete and getRandom set (the "RandomizedSet" interview problem) combines a list with a dict from value to index, deleting by swapping with the last element. It is built step by step in Designing Data Structures.

Recognizing a hashing problem

Clue in the problem Likely tool
"Does X exist?", "any duplicate?" set
"Find a pair/partner with property" dict value -> index
"Group / classify equal things" dict canonical-key -> list
"Count occurrences", "most frequent" Counter
"Subarray with sum / balance equal to ..." dict of prefix sums
"Do not use sorting", "O(n) time" hashing instead of sorting

The cost to remember: hashing usually trades O(n) extra space for removing a factor of n (or log n) from the time. If memory is tight or the data is already sorted, two pointers or sorting may be better. If the keys are small integers in a known range, a plain array of counts is faster than a dict.

Common mistakes

  • Inserting into the dict before checking in Two Sum, which can pair an element with itself.
  • Forgetting {0: 1} in the prefix-sum counter.
  • Using a list as the group key instead of a tuple or string.
  • Assuming hash lookups are always cheap. Hashing a long string key costs O(length), so n lookups of keys of length k cost O(n ยท k).
  • Counting a run from every member in the consecutive-sequence problem; only start at numbers without a predecessor.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In Two Sum with a dictionary, why do we check for the partner before storing the current number?

    If we stored x first, then looking for target - x could find x itself when 2x equals the target, producing a pair that uses one element twice.
  2. 2. What is the time complexity of Longest Consecutive Sequence with a set?

    Only numbers whose predecessor is missing start a run, and every number belongs to one run, so the total work across all runs is O(n).
  3. 3. Why is {0: 1} the starting dictionary in Subarray Sum Equals K?

    A subarray starting at index 0 has sum equal to a prefix sum minus the empty prefix (0). Seeding the count of prefix 0 with 1 lets that case be found.
  4. 4. Which key correctly groups anagrams?

    Sorted letters are identical for all anagrams. A list of counts has the right idea but lists are unhashable; you would need a tuple.
  5. 5. What is the space complexity of the hashing solution to Contains Duplicate?

    In the worst case (no duplicates) the set stores every element.

Summary

  • Hashing patterns: seen-set, value -> index, canonical key -> group, prefix sum -> count, and frequency tables.
  • Decide what the key should be: the partner value you need, a canonical form, or a prefix sum.
  • Typical gain: O(nยฒ) brute force becomes O(n) time at the cost of O(n) space.
  • In Two Sum check for the partner before inserting; in prefix-sum counting seed with {0: 1}; in consecutive sequences only start at run beginnings.
  • Prefer a plain array of counts when keys are small integers, and two pointers when data is sorted.

Next: Bloom Filters and Probabilistic Sets