14

Hashing & Prefix Sums

Trade a little memory for instant lookups, and precompute sums so every range answer is one subtraction.

beginner~80 min5 simulations13 problems

▶ guided lesson⚡ 1-minute summary↻ 15 recall cards

before this: Arrays & Strings · Big-O · Java Toolkit

01 · why it exists

Why this exists, and the weight it carries

since1953

Hash table

Hans Peter Luhn; Gene Amdahl, Elaine M. McGraw (née Boehme), Nathaniel Rochester, Arthur Samuel (IBM); Arnold Dumey; W. Wesley Peterson

In January 1953 Hans Peter Luhn wrote an internal IBM memo that put keys into numbered buckets and chained the overflow — one of the first uses of linked lists. At about the same time, Gene Amdahl, Elaine McGraw (née Boehme), Nathaniel Rochester and Arthur Samuel used hashing in an assembler for the IBM 701; Amdahl is credited with open addressing with linear probing. Arnold Dumey gave the first published description in 1956, and W. Wesley Peterson's 1957 paper studied open addressing in depth. Knuth's The Art of Computer Programming, Vol. 3 (§6.4), tells the full story.

the problem it solvedFinding a record by its key in about one step, instead of scanning everything or keeping the data sorted.

its jobs today

  • Java's HashMap/HashSet, Python's dict and JavaScript's Map: the default key → value store in every mainstream language.
  • Caches and databases: key–value stores like Redis, plus hash indexes and hash joins inside databases.
  • Git stores each loose object under .git/objects/, in a folder picked by the first two hex digits of the object's hash.

the weight it carries

Illustrative: 1 crore (10,000,000) UPI transaction ids, and each new payment must be checked against them for a repeat. Linear scan: up to 1 crore comparisons per check. Sorted array + binary search: ⌈log₂ 10⁷⌉ = 24 comparisons, but every insert shifts data. HashSet: a short chain — fewer than 2 key comparisons on average at load factor 0.75 — for both checks and inserts.

without it

Every "have I seen this?" or "what's stored under this key?" would cost O(n), or O(log n) with sorted structures — caches, compilers and deduplication would all slow down by orders of magnitude.

when · why · how

when
You look things up, insert or delete by key, and you don't need the keys in sorted order.
why
O(1) average per operation (O(log n) worst case in Java 8+), paid for with O(n) extra memory and no ordering. Need order or nearest-key queries? TreeMap, O(log n).
how
Map<K, V> map = new HashMap<>(); with get, put, getOrDefault, merge, computeIfAbsent; Set<T> seen = new HashSet<>(); where add returns false on repeats.

02 · plain english

The idea in 30 seconds

A hash function turns a key into an array index, so finding a key is one jump instead of a scan: O(1) on average.

A prefix sum array stores running totals once, so the sum of any range is prefix[r+1] − prefix[l]: O(1) per question.

Together they solve "count subarrays with sum k" in one pass: remember every prefix sum you've seen in a HashMap.

picture this

Hashing is how Git stores your files: it hashes each object's content, and the first two hex digits of that hash pick one of 256 folders under .git/objects/. Finding an object is one jump into one small folder, never a search through all of them. A prefix sum is a cricket scorecard's running total: runs scored between over 10 and over 20 = total after 20 − total after 10.

03 · remember

What you must know

  • Hash → bucket: index = hash(key) mod capacity. Different keys can land in the same bucket (a collision); Java keeps them in a chain (separate chaining) and tells them apart with equals.
  • Load factor 0.75: when size > 0.75 × capacity, HashMap doubles its table and re-hashes every entry. One resize is O(n), but they're rare, so put is O(1) amortized.
  • Java 8+ treeification: if one bucket grows past 8 entries and the table has at least 64 buckets, that chain becomes a red-black tree, so even a bad bucket costs O(log n), not O(n). With a smaller table, Java resizes instead.
  • equals/hashCode contract: equal objects must have equal hash codes. Override both or neither, and never mutate a key while it's inside a map.
  • Pick the flavour: HashMap/HashSet = fastest, no order · LinkedHashMap = insertion (or access) order · TreeMap/TreeSet = sorted, O(log n), floor/ceiling queries.
  • Counting is the #1 hashing pattern: map.merge(x, 1, Integer::sum). If keys are small integers or letters, an int[] is a faster "perfect" hash table.
  • One-to-one mappings need two maps: "each letter stands for one word and no two letters share a word" is two rules, so check both directions.
  • Prefix sums: prefix[i+1] = prefix[i] + nums[i] with prefix[0] = 0. The leading zero removes the "range starts at 0" special case.
  • Prefix sum + HashMap: a subarray (j..i] sums to k exactly when prefix[i] − prefix[j] = k. So at each i, ask the map how many earlier prefixes equal prefix[i] − k. This works with negative numbers, where sliding window fails.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

HashMap.put in 3D: hash, bucket, chain

Each key is hashed to a bucket. Collisions chain up; equal keys overwrite instead of duplicating.

loading simulation…
sim

Load factor 0.75: resize and rehash

Start small and watch the table double. Every entry moves, because its bucket depends on the capacity.

loading simulation…
sim

Build a prefix-sum array, then answer a range in O(1)

Each prefix cell reuses the one before it. A range sum is the difference of two cells.

loading simulation…
sim

2D prefix sums as a 3D landscape

Every cell = itself + up + left − up-left. Any rectangle is four lookups.

loading simulation…
sim

Prefix sum + HashMap: count subarrays that sum to k

The map remembers every prefix sum seen so far. A hit means a subarray that ends here sums to k.

loading simulation…

05 · cost

Time & space, explained

Hash-based collections (Java 8+)
AverageWorst casewhy
HashMap put / get / containsKey / removeO(1)O(log n)Average: one hash plus a short chain. Worst: everything collides into one bucket, which Java turns into a red-black tree (O(n) before Java 8, or if keys aren't Comparable).
HashMap put that triggers a resizeO(1) amortizedO(n) for that one callDoubling re-hashes all n entries, but it happens only after n/2 cheap puts, so the cost spreads to O(1) each.
HashSet add / contains / removeO(1)O(log n)A HashSet is a HashMap with a dummy value, so it inherits the same costs.
Iterate a HashMap / HashSetO(n + capacity)O(n + capacity)The iterator visits every bucket, empty or not. This rarely matters, but it explains why huge, mostly empty maps iterate slowly.
LinkedHashMap put / getO(1)O(log n)It's a HashMap plus a doubly linked list through the entries, and updating that list is O(1).
TreeMap / TreeSet put / get / floorKey / ceilingKeyO(log n)O(log n)A red-black tree stays balanced, so its height is always O(log n).
int[] counting array (keys in 0..m−1)O(1)O(1)The key is the index, so there's no hashing and no collisions. It costs O(m) memory.
Prefix sums
TimeExtra spacewhy
Build 1D prefix arrayO(n)O(n)One addition per element, stored in an array of n + 1 slots.
Range sum query (after building)O(1)O(1)It's one subtraction: prefix[r+1] − prefix[l].
Range sum without prefix sumsO(n) per queryO(1)You re-add the range every time, so q queries cost O(n·q).
Change one nums[i], then queryO(n) per updateO(n)Every prefix after i changes. For many updates use a Fenwick or segment tree (Range Queries chapter): O(log n) each.
Build 2D prefix (r × c)O(r·c)O(r·c)Each cell is filled once from three neighbours already computed.
2D rectangle queryO(1)O(1)Four lookups: whole − above − left + corner.
Count subarrays with sum k (prefix + HashMap)O(n)O(n)One pass. Each step does one O(1) map lookup and one O(1) update.

06 · java

Raw vs Collections Framework

A hash table by hand (separate chaining)

javaChainedHashMapjava.util.*
class ChainedHashMap<K, V> {    private static final double LOAD_FACTOR = 0.75;     private static class Node<K, V> {        final K key;        V value;        Node<K, V> next;         Node(K key, V value) {            this.key = key;            this.value = value;        }    }     private Node<K, V>[] table;    private int size = 0;     ChainedHashMap(int initialCapacity) {        table = newTable(initialCapacity);    }     /** hashCode → bucket index. The mask drops the sign bit so the index is never negative. */    static int indexFor(Object key, int capacity) {        return (key.hashCode() & 0x7fffffff) % capacity;    }     public void put(K key, V value) {        int index = indexFor(key, table.length);        for (Node<K, V> node = table[index]; node != null; node = node.next) {            if (node.key.equals(key)) {                node.value = value; // same key → overwrite, size unchanged                return;            }        }        append(index, new Node<>(key, value)); // new key → add to the chain        size++;        if (size > table.length * LOAD_FACTOR) resize(); // too full?    }     public V get(K key) {        for (Node<K, V> node = table[indexFor(key, table.length)]; node != null; node = node.next) {            if (node.key.equals(key)) return node.value;        }        return null;    }     /** Double the table and move every entry to its bucket in the new table. */    private void resize() {        Node<K, V>[] old = table;        table = newTable(old.length * 2);        for (Node<K, V> head : old) {            for (Node<K, V> node = head; node != null; node = node.next) {                append(indexFor(node.key, table.length), new Node<>(node.key, node.value));            }        }    }     private void append(int index, Node<K, V> fresh) {        if (table[index] == null) {            table[index] = fresh;            return;        }        Node<K, V> tail = table[index];        while (tail.next != null) tail = tail.next;        tail.next = fresh;    }     public int size() { return size; }     public int capacity() { return table.length; }     @SuppressWarnings("unchecked")    private static <K, V> Node<K, V>[] newTable(int capacity) {        return (Node<K, V>[]) new Node[capacity];    }}
  • This is the same idea as java.util.HashMap, simplified so every line is readable.
  • The real HashMap also mixes the high bits into the low ones (h ^ (h >>> 16)) and uses hash & (capacity − 1) instead of %. That's why its capacity is always a power of two (default 16).
  • HashMap allocates its table lazily on the first put. The default threshold is 16 × 0.75 = 12 entries.
  • Java 8+ appends new entries to the tail of a chain and turns a chain into a red-black tree past 8 entries (when capacity ≥ 64). If a resize splits it down to 6 or fewer, it turns back into a list.

Counting: int[] vs HashMap

javaint[26] counterjava.util.*
class ArrayCounting {    /** Frequency of each lowercase letter. An int[26] is a perfect hash table for 'a'..'z'. */    static int[] letterCounts(String s) {        int[] count = new int[26];        for (char c : s.toCharArray()) count[c - 'a']++;        return count;    }     static boolean isAnagram(String a, String b) {        return Arrays.equals(letterCounts(a), letterCounts(b));    }}
  • Use int[26] (or int[128] for ASCII) when keys are small and dense. There's no boxing, no hashing, and it's often several times faster.
  • Use a HashMap when keys are big, sparse, negative, or not numbers.
  • merge(k, 1, Integer::sum) means "insert 1, or add 1 to what's there". getOrDefault avoids null checks. computeIfAbsent builds a list per key on demand.

Custom keys: the equals/hashCode contract

javaPoint + recordjava.util.*
/** A custom key: equals and hashCode must agree, and both must use only final fields. */final class Point {    private final int x;    private final int y;     Point(int x, int y) {        this.x = x;        this.y = y;    }     @Override    public boolean equals(Object o) {        if (this == o) return true;        if (!(o instanceof Point other)) return false;        return x == other.x && y == other.y;    }     @Override    public int hashCode() {        return 31 * x + y; // equal points → equal hash codes (the contract)    }} /** Since Java 16 a record writes equals, hashCode and toString for you. */record Cell(int row, int col) {}
  • If a.equals(b) then a.hashCode() == b.hashCode(). The reverse doesn't have to hold: equal hashes can belong to different keys (collisions).
  • Override equals without hashCode and two equal points land in different buckets, so contains returns false.
  • Prefer record keys (Java 16+). They are immutable and generate a correct equals/hashCode for you.
  • Never use a mutable object as a key and then change it. Its hash changes, and the entry is lost in the wrong bucket.

HashSet vs TreeSet vs LinkedHashSet

javathree flavoursjava.util.*
class SetFlavours {    /** HashSet: O(1) average, but iteration order is unspecified. */    static boolean hasDuplicate(int[] nums) {        Set<Integer> seen = new HashSet<>();        for (int x : nums) if (!seen.add(x)) return true; // add returns false if already present        return false;    }     /** TreeSet: O(log n), always sorted, supports floor/ceiling queries. */    static List<Integer> sortedUnique(int[] nums) {        TreeSet<Integer> set = new TreeSet<>();        for (int x : nums) set.add(x);        return new ArrayList<>(set);    }     static Integer smallestAtLeast(TreeSet<Integer> set, int x) {        return set.ceiling(x); // null if none    }     /** LinkedHashSet / LinkedHashMap: O(1) average and remembers insertion order. */    static List<Integer> uniqueInFirstSeenOrder(int[] nums) {        Set<Integer> set = new LinkedHashSet<>();        for (int x : nums) set.add(x);        return new ArrayList<>(set);    }}
  • HashSet/HashMap iteration order is unspecified and can change after a resize. Never rely on it.
  • TreeSet/TreeMap keep keys sorted and add floor, ceiling, first, last and headMap/tailMap in O(log n).
  • LinkedHashMap remembers insertion order. With new LinkedHashMap<>(16, 0.75f, true) plus removeEldestEntry, it becomes an LRU cache (see Linked Lists).

Range sums: re-add every time vs precompute

javaloop per queryjava.util.*
class LoopEveryQuery {    /** Sum of nums[left..right] by walking the range: O(n) per query. */    static long rangeSum(int[] nums, int left, int right) {        long sum = 0;        for (int i = left; i <= right; i++) sum += nums[i];        return sum;    }}
  • Precomputing pays off as soon as there is more than a handful of queries: O(n + q) instead of O(n·q).
  • Use long for prefix sums when values or lengths are large. A running total overflows int long before any single element does.

Library prefix sums and 2D prefix sums

java2D prefixjava.util.*
class PrefixSum2D {    private final long[][] p; // p[r][c] = sum of the rectangle from (0,0) to (r-1,c-1)     PrefixSum2D(int[][] grid) {        int rows = grid.length, cols = rows == 0 ? 0 : grid[0].length;        p = new long[rows + 1][cols + 1]; // extra zero row and column        for (int r = 0; r < rows; r++) {            for (int c = 0; c < cols; c++) {                // up + left counts the up-left block twice, so subtract it once                p[r + 1][c + 1] = grid[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];            }        }    }     /** Sum of the rectangle (r1,c1)..(r2,c2), inclusive, in O(1). */    long sumRegion(int r1, int c1, int r2, int c2) {        return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];    }}
  • Arrays.parallelPrefix gives inclusive running sums (no leading 0). Interviewers usually expect the hand-written loop.
  • In 2D, the extra zero row and column play the same role as prefix[0] = 0 in 1D.
Java API you will actually use
calldoescost
map.put(k, v) / map.get(k)Insert/overwrite, or read (null if missing)O(1) avg
map.getOrDefault(k, 0)Read with a fallback, so there's no null checkO(1) avg
map.merge(k, 1, Integer::sum)Insert 1, or add 1 to the existing count — returns the new countO(1) avg
map.computeIfAbsent(k, x -> new ArrayList<>()).add(v)Group values under a keyO(1) avg
map.putIfAbsent(k, v)Store v only if k is new; returns the old value (or null) — handy for one-to-one checksO(1) avg
map.containsKey(k) / map.remove(k)Check membership / deleteO(1) avg
map.entrySet()Iterate key–value pairs together (faster than keySet + get)O(n + capacity)
set.add(x) / set.remove(x)Return false if x was already there / wasn't there: a free membership checkO(1) avg
treeMap.floorKey(k) / ceilingKey(k)Largest key ≤ k / smallest key ≥ kO(log n)
new HashMap<>(expected * 4 / 3 + 1)Pre-size to avoid resizes when you know the countO(capacity)
Objects.hash(a, b, c) / Objects.equals(a, b)Quick hashCode for custom keys (boxes its arguments) / null-safe equality for boxed valuesO(fields) / O(1)
Math.floorMod(x, k)Remainder in 0..k−1 even for negative xO(1)

"Have I seen this before?"

→ HashSet

O(1) average add/contains, and add returning false is the check.

Count occurrences

→ int[] if keys are small and dense, else HashMap + merge

The array skips hashing and boxing. The map handles any key.

Value → index (complement lookups)

→ HashMap<Integer, Integer>

One-pass Two Sum style lookups.

One-to-one pairing (pattern ↔ word)

→ Two maps, one per direction (or two int[256] for chars)

One map can't notice two keys sharing the same value.

Keys in sorted order, or nearest key ≤ / ≥ x

→ TreeMap / TreeSet

O(log n) with ordered queries a hash map can't do.

Iterate in the order keys were inserted

→ LinkedHashMap / LinkedHashSet

Hash speed plus predictable order.

Many range-sum queries on a fixed array

→ Prefix-sum array

O(n) once, then O(1) per query.

Range sums with frequent updates

→ Fenwick / segment tree

O(log n) update and query, where prefix sums need O(n) per update.

07 · recognise

Spot the pattern

"Find a pair / complement" in an unsorted array, return indices

HashMap value → index, look up target − x before storing x

"Duplicate", "seen before", "unique", "first repeating"

HashSet (add returns false on repeats)

"Frequency", "most common", "anagram", "top k"

Counting map or int[26]; then bucket sort or a heap

"Can you build X from the letters of Y?"

Count Y's letters, then spend them on X (int[26])

"Longest palindrome you can build" from given letters

Use every pair; one leftover letter can sit in the middle

"Pattern", "isomorphic": each symbol must stand for exactly one thing

Two maps (or two arrays), one per direction

"Sum of a range" asked many times on a fixed array

Prefix sums: build once, answer in O(1)

"Number of subarrays with sum = k" and values can be negative

Prefix sum + HashMap of counts (sliding window breaks with negatives)

"Longest subarray with equal 0s and 1s" / "balanced"

Map 0 → −1, then the longest subarray with sum 0. Store the first index of each prefix

"Divisible by k", "multiple of k"

Prefix sums mod k: equal remainders bracket a divisible subarray

O(n) required and sorting is too slow

Hash set or map: trade O(n) memory for time

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Forgetting seen.put(0, 1) (or prefix[0] = 0). Subarrays that start at index 0 are silently missed.
  • Storing into the map before looking up. In Two Sum, [3] with target 6 would pair 3 with itself.
  • Comparing Integer objects with == or !=. It works only for −128..127 (the Integer cache), then breaks. Use .equals, Objects.equals, or unbox to int.
  • Java's % can be negative: -7 % 5 == -2. Use Math.floorMod(x, k) or ((x % k) + k) % k for remainders.
  • Overriding equals without hashCode, or mutating a key after inserting it. The entry becomes unreachable.
  • Relying on HashMap iteration order. It's unspecified and may change after a resize or between Java versions.
  • Using sliding window for "subarray sum = k" with negative numbers. Growing the window no longer increases the sum.
  • Iterating nums instead of the HashSet in Longest Consecutive Sequence. With many duplicates, sequence starts get re-walked and it degrades towards O(n²).
  • Checking a one-to-one mapping in only one direction (Isomorphic Strings, Word Pattern): two keys can quietly share one value.

tricks

  • Say "O(1) average" in interviews, and mention the O(log n) worst case from Java 8 treeification. It shows depth.
  • Name the map by its meaning: seen, indexOf, countOf, firstIndexOfBalance. Half the bugs vanish.
  • For prefix-sum problems, write the identity on the whiteboard first: sum(j..i) = P[i+1] − P[j]. Then the map key falls out.
  • Before reaching for a map, ask: are the keys small integers? Then an array is simpler and faster.
  • Dry-run with a tiny input that has a 0 or a negative. These break naive window solutions and confirm your map logic.
  • Pre-size maps when you know the size: new HashMap<>(n * 4 / 3 + 1) avoids every resize (Java 19+ also has HashMap.newHashMap(n)).
  • Bas itna yaad rakho: a map answers "what do I know about this key?"; a prefix array answers "how much up to here?". Most problems in this chapter are one of those two questions.

09 · why & how

Questions you might be too shy to ask

If collisions exist, how can lookups be O(1)?

Because collisions are rare when the table isn't too full. With load factor ≤ 0.75 and a good hash function, the expected chain length is a small constant, so you check about one or two keys. The worst case (everything in one bucket) is O(n) for a plain chain. Since Java 8 a long chain becomes a red-black tree, which brings it down to O(log n) (guaranteed when the keys are Comparable, like Integer and String).

What is a hash code, really? Is it the object's memory address?

It is just an int that hashCode() returns. HashMap squeezes it down to a bucket number. Each class decides how to compute it: Integer.valueOf(5).hashCode() is 5, and a String mixes its characters ("ab".hashCode() is 97 * 31 + 98 = 3105). The default Object.hashCode() is identity-based, but the Java spec does not promise it is an address — never treat it as one.

Why does HashMap resize at 0.75, not 1.0?

It's a speed–memory trade-off. A fuller table means more collisions and longer chains; an emptier one wastes buckets. The HashMap Javadoc calls the default 0.75 "a good tradeoff between time and space costs"; you can pass another value to the constructor, but you rarely need to.

Why is a resize not a disaster if it touches every element?

Because it doubles the capacity. A resize from capacity m to 2m happens at 0.75m entries, and the next one only at 1.5m, so another 0.75m cheap puts come first: as many as the entries just copied. Spread over those puts, the O(n) copy adds only O(1) per put. That's what amortized O(1) means.

What exactly is the equals/hashCode contract, and what breaks if I ignore it?

Equal objects must return the same hashCode. HashMap first jumps to the bucket chosen by hashCode, and only then calls equals. If two equal points return different hash codes, the lookup usually checks the wrong bucket. Even in the same bucket, HashMap compares the hash codes before it calls equals. Either way it never calls equals and says "not found".

Can I use an int[] as a HashMap key, like [1, 2]?

Technically yes, but it won't work the way you want. Arrays do not override equals/hashCode, so two arrays with the same numbers are different keys. new int[]{1, 2}.equals(new int[]{1, 2}) is false. Use a key whose equals compares contents: a String like Arrays.toString(arr), a List.of(1, 2), or a record. Dhyan do: never change a list after using it as a key.

HashMap or TreeMap?

Default to HashMap: O(1) average. Pick TreeMap only when you need order: sorted iteration, smallest/largest key, or "nearest key ≤ x". Then O(log n) is the price of that order.

Why does the prefix array have n + 1 slots?

prefix[0] = 0 stands for "sum of nothing". Then the sum of nums[l..r] is always prefix[r+1] − prefix[l], including when l = 0. Without it you'd need an if for ranges that start at the beginning.

Why put 0 → 1 in the map for Subarray Sum Equals K?

It's the HashMap version of prefix[0] = 0. If the running sum itself equals k, the matching "earlier prefix" is the empty prefix, and the map must already contain it.

I keep mixing up sum - k and k - sum, and why do we add a count instead of just 1?

A subarray ending here sums to k when current - earlier = k, so the earlier prefix must be current - k. Write that line first, then the code follows. Several earlier prefixes can have that same value. Each one is the start of a different subarray. Example: [1, -1, 1], k = 1. Prefixes are 0, 1, 0, 1. At the last 1 we need 0, seen twice → [1, -1, 1] and [1]. So add 2, not 1.

Subarray Sum Equals K stores a count, Contiguous Array stores the first index. How do I know which to store?

Store what the question asks about. "How many subarrays?" → store how many times each prefix appeared. "Longest subarray?" → store the first index of each prefix, and never overwrite it (the earliest start gives the longest span). "Shortest subarray?" → store the latest index, overwriting each time.

When do I use sliding window and when prefix sum + map?

Sliding window needs a monotonic sum: all numbers non-negative, so growing the window never decreases the sum. With negatives, or when you must count exact sums, use prefix sum + HashMap.

Isomorphic Strings: one map from s to t feels enough. Why two?

One map only checks that each character of s always becomes the same character. It can't see two different characters becoming the same one: "badc" → "baba" maps b→b and d→b without any conflict in the s → t map. The second map, t → s, catches exactly that.

I gave a HashMap solution and the interviewer asked, "Can you do it without extra space?" What now?

Don't panic — they are testing whether you know the trade-off. The usual answer is sorting: Contains Duplicate becomes "sort, then compare neighbours" in O(n log n) time and only the sort's own memory. Say the cost out loud: "I save memory, but time goes from O(n) to O(n log n), and sorting in place changes the input. Is that okay?" If you need original indices (Two Sum), sorting loses them, so mention that too.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #1
    Two Summust-do
    EasyGoogleAmazonMicrosoftAdobeBloomberg+1
  2. #217
    Contains Duplicatemust-do
    EasyNetflixAirbnbBloombergMicrosoftAmazon+1
  3. #383
    Ransom Note
    EasyAppleMicrosoftAmazon
  4. #409
    Longest Palindrome
    EasyGoogleAmazonMicrosoft
  5. #205
    Isomorphic Strings
    EasyLinkedInBloombergAmazonGoogle
  6. #290
    Word Pattern
    EasyBloombergGoogleAmazon
  7. #128
    Longest Consecutive Sequencemust-do
    MediumBloombergWalmartAmazonByteDance / TikTokGoogle+1
  8. #36
    Valid Sudoku
    MediumAppleUberAmazonMicrosoft
  9. #303
    Range Sum Query - Immutablemust-do
    EasyInfosysMetaAmazonBloombergGoogle+1
  10. #304
    Range Sum Query 2D - Immutable
    MediumGoogleAmazonMeta
  11. #560
    Subarray Sum Equals Kmust-do
    MediumMetaInfosysMicrosoftAmazonBloomberg+1
  12. #525
    Contiguous Array
    MediumMetaAmazonGoogle
  13. #974
    Subarray Sums Divisible by K
    MediumAmazonMeta

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #347
    Top K Frequent Elements
    Mediumin Heaps

    Count with a HashMap first; bucketing values by frequency then finishes the job in O(n) (its bucket-sort approach).

  2. #49
    Group Anagrams
    Mediumin Arrays & Strings

    Hashing with a canonical key: every anagram produces the same letter-count string, so a HashMap buckets them in one pass.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    A hash table turns a key into a bucket index (hash & (capacity − 1)), so get / put / contains cost O(1) on average.

  2. what it is

    A prefix sum stores running totals once: sum(l..r) = p[r + 1] − p[l] — one subtraction per query.

  3. use it when

    Seen before? → HashSet. Value → index or count → HashMap. Many range sums → prefix array. Sum = k with negatives → prefix + map.

  4. cost

    HashMap: O(1) average, O(log n) worst (Java 8+ trees), O(n) memory. Prefix sums: O(n) build, O(1) query, O(n) per update.

  5. template

    seen.put(0, 1); then per x: sum += x; count += seen.getOrDefault(sum - k, 0); seen.merge(sum, 1, Integer::sum);

  6. trap

    Override equals without hashCode (or change a key after put) and the entry is lost: lookups go to the wrong bucket.

  7. trap

    Integer objects compared with == or != work only for −128..127. Use .equals, Objects.equals, or unbox to int.

  8. trap

    Java's % can be negative: -7 % 3 == -1. Use Math.floorMod(x, k) when the remainder is a map key.

  9. pro tip

    Keys small and dense (letters, 1..n, remainders)? An int[] is a perfect hash table — no hashing, no boxing.

  10. pro tip

    One-to-one mapping (isomorphic, word pattern)? Two maps, one per direction — a single map can't see two keys sharing a value.

12 · recall

Flip, remember, repeat

card 1 / 15
recall

HashMap get/put in Java 8+: average and worst-case cost?

tap or Space to flip ↻

Question 1: HashMap get/put in Java 8+: average and worst-case cost?

13 · check yourself

Quick quiz

  1. A HashMap has capacity 16 and the default load factor. On which put does it resize?

  2. Two keys have the same hashCode but are not equal. What does HashMap do?

  3. You override equals in Point but not hashCode. What usually happens to `set.contains(new Point(1, 2))` after adding an equal point?

  4. nums = [2, 4, 1, 3]. prefix = [0, 2, 6, 7, 10]. What is the sum of nums[1..3]?

  5. Why does Subarray Sum Equals K need a HashMap instead of a sliding window?

  6. In Java 8+, when does a HashMap bucket become a red-black tree?

  7. In Java, what is `-7 % 3`?

  8. With only a map s → t, which pair would be wrongly reported as isomorphic?

  9. What is the longest palindrome you can build from the letters of "aaabbbcc"?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one