Hashing
Why hashing exists — the story
You get an interview question you've seen before: Two Sum. Given nums = [2, 7, 11, 15] and target = 9, return the indices of the two numbers that add up to 9. Easy. You write two nested loops. Every pair. Return [0, 1]. Done.
The interviewer nods, then says: "Great. Now n = 10⁷."
Your O(n²) solution is now 5 × 10¹³ operations — about 20 minutes at 40M ops/sec. The interviewer will not wait 20 minutes. And here's the maddening part: for each nums[i], you know exactly what number you need — it's target - nums[i]. You don't need to scan for it; you need to look it up. Scanning is what makes the loop O(n²). Lookup is what turns it O(n).
The idea that makes lookup fast is a hash table: a data structure that maps keys to values with average O(1) insert and lookup — no scanning, no comparing, no sorting. Give it a key, get back the value in constant time. For Two Sum, walk the array once; at each nums[i] ask "have I seen target - nums[i] already?" If yes, return. If no, remember nums[i] and continue. One pass. 20 minutes → 100 milliseconds. A twelve-thousand-times speedup for four lines of code.
But hash tables are more than just fast Two Sum. Anywhere a brute-force says "for each element, look through all the others", a hash map lets you swap that inner scan for a lookup. Group anagrams? Instead of comparing every pair, hash each word to a canonical fingerprint and bucket. Longest consecutive sequence? Instead of sorting, dump into a set and expand only from the "start" of each run. Streak detection, frequency counting, complement lookup, cycle detection in a functional graph — hashing is the single most productive tool in a competitive programmer's toolbox.
The catch, and it's a real one: hash tables can degrade to O(n) per operation if the hash function is bad or an adversary crafts colliding keys. Understanding when this happens — and how Java's HashMap mitigates it — is the difference between a candidate who says "hashing" and one who says "HashMap with treeified buckets past load factor 0.75, average O(1)."
The core idea — replace scans with lookups
Hashing — one lookup instead of a scan
Type a key and press Insert or Lookup. The hash function is h(k) = Σ k[i] × 31i mod 7. Same hash → same bucket → collision (chained).
cat) = 6cat, act, tac — same hash, same bucket, chain grows.Every hashing solution has the same three-part shape:
- Choose a key — an integer, a string, a canonical fingerprint of some structure. The key is what makes two things "the same".
- Choose a value — usually the index, a count, or a linked structure holding more state.
- Walk the input once, at each element (a) asking the hash table a question about what you've seen, and (b) updating the table with the current element.
The engineering discipline is: before writing the loop, decide what the key is, what the value is, and what question you ask the hash at each step. Half of the "I got Two Sum on a whiteboard and blanked" stories come from starting the loop with a fuzzy plan.
When to use it — recognition signals
- "Pair / triplet / quadruple summing to target" — complement lookup. Two Sum, 3Sum (hash-based variant), 4Sum.
- "Any duplicate?" / "first non-repeated" — hash set membership; hash map with counts.
- "Group by some property" — anagrams (sorted-string key), isomorphic strings (pattern signature), group shifted strings (relative-offset signature).
- "Streak / longest consecutive run" — dump values into a
HashSet, then expand from each element that starts a run. - "Have I visited this state?" — cycle detection in a functional graph (Happy Number), state deduplication in BFS.
- "Distinct elements in a window" — a sliding-window frequency map is a hashing inside a two-pointer.
- "Given operations mixed with queries on values" — key by value, store position or count.
- "Return the k-th most X" — hash to count, then reduce.
- "Random access on arbitrary-shaped keys" — arrays only key by integer; hash maps key by anything with
hashCode+equals. Tuples, strings, records, canonical forms.
When NOT to use it
- The keyspace is a small dense integer range — arrays are faster and simpler. Counting sort, radix sort, and array-indexed lookups beat HashMap for ASCII-character-frequency problems.
- You need ordered iteration or range queries — hash maps are unordered by contract. Use
TreeMap(log n but ordered) or maintain a parallel sorted structure. - Memory is tight — HashMap has overhead: each entry is a wrapper node with a hash int, key ref, value ref, next ref. For
n = 10⁷Integer → Integermappings, expect ~500 MB. A primitiveint[]beats it 100× on memory. - You need worst-case O(1) — hash maps are average O(1), worst-case O(n) if all keys collide. For adversarial or crypto-sensitive contexts (rate limiter keys, DDoS vectors), use a
TreeMap(O(log n) worst-case) or a cryptographically strong hash. - The comparison you want isn't equality — hashing keys by equality doesn't help "find the closest match" or "range query." Use a BST or interval tree.
- You need to remember insertion order — plain
HashMapdoesn't; useLinkedHashMap(constant-factor overhead) or explicit ordering.
The templates
Template 1: Complement lookup (Two Sum family)
int[] twoSum(int[] a, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < a.length; i++) {
int need = target - a[i]; // partner we're looking for
if (seen.containsKey(need)) { // did we see the partner already?
return new int[]{seen.get(need), i};
}
seen.put(a[i], i); // remember this value for future queries
}
return new int[]{-1, -1};
}Invariant: seen contains exactly the values a[0..i-1] mapped to their indices. Complexity: O(n) average, O(n²) worst-case (if all values collide to one bucket). Trap: if the array has duplicates (a = [3, 3], target = 6), record after checking, not before.
Template 2: Canonical-key grouping (Group Anagrams)
List<List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> buckets = new HashMap<>();
for (String w : words) {
char[] chars = w.toCharArray();
Arrays.sort(chars); // sorted string is the canonical form
String key = new String(chars);
buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(buckets.values());
}Invariant: every string in bucket key has sortedChars(word) == key. Complexity: O(n · L log L) where L is average word length. Alternative canonical key: a length-26 int array of character counts, converted to a string — O(n · L) but with a larger constant.
Template 3: Frequency map with running counts (character-count problems)
Map<Character, Integer> freqs = new HashMap<>();
for (char c : s.toCharArray()) {
freqs.merge(c, 1, Integer::sum); // idiomatic Java: increment or insert
}Idiom to memorize: map.merge(key, 1, Integer::sum) is Java's canonical "increment counter" one-liner. Cleaner than map.put(key, map.getOrDefault(key, 0) + 1).
Template 4: HashSet for O(1) membership
Set<Integer> present = new HashSet<>();
for (int x : a) present.add(x);
// membership check anywhere:
if (present.contains(y)) { ... }Use HashSet when you only need presence, not a value payload. Half the memory of HashMap.
Complexity summary
| Operation | Average | Worst-case | Notes |
|---|---|---|---|
put / get / containsKey | O(1) | O(log n)† | †Java 8+: treeifies buckets past 8 collisions |
remove | O(1) | O(log n)† | |
| Iteration | O(n + capacity) | O(n + capacity) | Order is undefined |
| Space | O(n) | O(n) | ~48 bytes per entry in Java |
Rule of thumb: HashMap-based algorithms are O(n) average, but always state the O(1) qualification explicitly in interviews. Interviewers respect candidates who acknowledge the worst case.
Traps & gotchas — the 5 that fail candidates on interview day
Input a = [3, 3], target 6. If you put before checking, when you visit a[0] = 3, seen gets {3: 0}, then when you visit a[1] = 3, you look for 3, find it (yourself!), and return [0, 0] — wrong. Rule: check first, then put.
In Java, if you use a mutable object (a list, a char[]) as a HashMap key and modify it after insertion, its hashCode changes and the map cannot find it. map.containsKey(theSameObject) returns false. Rule: keys must be effectively immutable, or use immutable wrappers like String.
HashMap<Integer, Integer> boxes every primitive int into an Integer object. For n = 10⁷, that's 10⁷ heap allocations just for keys. Performance drops 5-10× vs. a primitive int[]. Rule: for dense integer keys, prefer a primitive array or a specialized library like Eclipse Collections' IntIntHashMap.
If you override equals but not hashCode (or vice versa), your custom class silently misbehaves as a HashMap key. Two objects that equals returns true for must return the same hashCode. Rule: always override both, or neither. IDE-generate them.
Java's String.hashCode() was famously predictable; an attacker sending crafted keys could force all hash buckets to collide, degrading a HashMap to O(n²). Rule: for user-controlled keys in a web service, use randomized hashing (Objects.hash with a per-instance seed) or a TreeMap. Java 8 mitigates this by treeifying buckets, but only if the key's Comparable — String is, custom classes may not be.
History — Dumey's 1956 memo at IBM
The hash-table idea was first written down in an internal IBM memo by Arnold Dumey in 1956, titled "Indexing for rapid random-access memory systems." Dumey proposed dividing the address space into "buckets" indexed by a key's remainder modulo a prime — the exact structure every modern hash table still uses. The technique was formalized by Wesley Peterson in 1957 and became a standard technique in Knuth's Sorting and Searching (1973).
Java's HashMap (1998, JDK 1.2) used separate chaining — collisions live in a linked list. In JDK 8 (2014), Josh Bloch and Doug Lea rewrote it to treeify buckets that exceed 8 collisions, capping worst-case from O(n) to O(log n). This mitigates hash-flooding DoS attacks that had plagued HashMap-based web services since 2011.
Google's BigTable (2006), Redis (2009), and Memcached (2003) are all — at their core — massive distributed hash tables. Every time you use a Map in Java, you're calling a subroutine invented in a 1956 memo.
Canonical problem walkthrough — Two Sum
Problem (↗ LeetCode): Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Assume exactly one solution exists; you may not use the same element twice.
Approach 1 — Brute force
Two nested loops.
int[] twoSumBrute(int[] a, int target) {
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] + a[j] == target) return new int[]{i, j};
return new int[]{-1, -1};
}Complexity: O(n²) time, O(1) space. For n = 10⁴, about 5·10⁷ ops — passes. For n = 10⁷, ~10¹⁴ ops — fails. State it, move on.
Approach 2 — Sort + two pointers (if we could)
Sort, then walk two pointers from the ends. Problem: sorting destroys the original indices. So we'd need to sort pairs of (value, index).
int[] twoSumSort(int[] a, int target) {
int n = a.length;
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) pairs[i] = new int[]{a[i], i};
Arrays.sort(pairs, (x, y) -> x[0] - y[0]);
int lo = 0, hi = n - 1;
while (lo < hi) {
int sum = pairs[lo][0] + pairs[hi][0];
if (sum == target) return new int[]{pairs[lo][1], pairs[hi][1]};
if (sum < target) lo++;
else hi--;
}
return new int[]{-1, -1};
}Complexity: O(n log n) time, O(n) space. Works, but the sort dominates. And we need to allocate the pairs array. Not the best.
Approach 3 — HashMap in one pass (the interview answer)
Walk the array once. At each a[i], check whether target - a[i] is already in the map (indexed by its position). If yes, return. If no, record a[i] and continue.
int[] twoSum(int[] a, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < a.length; i++) {
int need = target - a[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(a[i], i); // record AFTER checking
}
return new int[]{-1, -1};
}Complexity: O(n) time average, O(n) space.
Interview commentary:
- "Brute force is O(n²). We can do O(n) by remembering values we've seen."
- "For each
a[i], we needtarget - a[i]. If it's already in the map, we've found the pair." - "Record after checking, not before, so we don't match an element with itself."
- "Average O(1) per operation; worst case O(n) per op if adversarial collisions, but Java 8 HashMap treeifies past 8 collisions."
Complexity ladder
| Approach | Time | Space | When |
|---|---|---|---|
| Brute force | O(n²) | O(1) | Reference / very small n |
| Sort + two pointers | O(n log n) | O(n) | If sort is already needed for another reason |
| HashMap one-pass | O(n) avg | O(n) | Interview default |
Two Sum Easy
Try it yourself
Edit the Java code below and click ▶ Run tests to check it against real examples. Powered by Judge0; your code auto-saves in your browser.
Problem
Given an array nums and a target, return the indices of the two entries that add up to target. Exactly one pair works, and you can't reuse the same index.
Constraints: 2 ≤ nums.length ≤ 10⁴; the array is not sorted; values fit in int.
Example 1: nums = [2,7,11,15], target = 9 → [0,1] (since 2 + 7 = 9).
Example 2: nums = [3,3], target = 6 → [0,1] (two equal values must be different indices).
Solution — brute force
Nested loop: for each i, scan j > i for nums[i] + nums[j] == target. This is O(n²) time and O(1) space, and it is correct but too slow once n reaches 10⁴. The hash-map optimization avoids the inner scan by remembering values already seen and asking whether the current value's complement has appeared.
int[] twoSumBrute(int[] a, int target) {
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] + a[j] == target) return new int[]{i, j};
return new int[]{-1, -1};
}Brute-force cost: O(n²) time, O(1) space — too slow for n ≥ 10⁴.
Solution — optimized
The optimized one-pass map stores values already seen. At each index, check whether the exact complement is already behind you; checking before insert prevents using the same index twice.
Pattern. Complement lookup: replace nested search with one-pass hashing.
Steps.
- Create an empty hash map from value → index.
- Scan the array once. For each
a[i], computeneed = target - a[i]. - If
needis in the map, return{map[need], i}. - Otherwise
map[a[i]] = i. Check-then-insert (never the other way — an element would match itself).
Java.
int[] twoSum(int[] a, int target) {
Map<Integer,Integer> seen = new HashMap<>();
for (int i = 0; i < a.length; i++) {
Integer j = seen.get(target - a[i]);
if (j != null) return new int[]{j, i};
seen.put(a[i], i);
}
return new int[]{-1,-1};
}Time Complexity
Existing summary: Time O(n) · Space O(n).
The scan is O(n) expected time because each element performs one hash lookup and one hash insert on average.
Space Complexity
Space is O(n) in the worst case because the map may store every prior value before the answer appears.
Learning notes
- Why
Map<Integer,Integer>? — we need the partner value and must return its index. - Why compute
target - a[i]? — that is the only value that completes the pair. - Why check before
seen.put? — otherwise an element could match itself. - Why use
Integer j? —nullcleanly means the complement was absent. - Why return
{j, i}? —jis the earlier stored index.
For each x, the partner you need is target - x. Remember values as you go; check before inserting.
When at index i, the map holds every value at indices < i with its index.
a=[2,7,11,15], target=9. At i=1 (value 7) the partner is 9−7=2, already stored from i=0 → return [0,1]. No full rescan needed.
"I first confirm there is exactly one answer and I should return indices, not values. I start with brute force by checking every pair, which is O(n²) time and O(1) space. I optimize by storing seen values in a hash map and checking target - a[i] during one scan, giving O(n) time and O(n) space."
Inserting into the map before the check makes an element match itself. Example: nums=[3,2,4], target=6. If you put(3,0) first, then check for target-3=3, you find yourself and emit (0,0). Check first, insert after.
Hashing. In a sorted array the same task becomes two pointers in O(1) space; the sorted-vs-unsorted choice recurs throughout.
Same pattern, new tweaks
Every variation below changes exactly one constraint — and that one change dictates the approach. This is the real skill: recognizing which lever moved.
| Variation | The one thing that changes | So the approach becomes… | Time · Space |
|---|---|---|---|
| Two Sum II — sorted input | the array is already sorted | drop the map — converge two pointers from both ends (sum too small → lo++; too big → hi--) | O(n) · O(1) |
| 3Sum | need three numbers summing to 0, no duplicate triplets | sort; fix a[i], then two-pointer the rest for −a[i]; skip equal values to dedupe | O(n²) · O(1) |
| 4Sum | four numbers summing to target | sort; fix two indices with nested loops, two-pointer the remaining pair | O(n³) · O(1) |
| Two Sum III — design | numbers arrive over time, many find queries | keep a running frequency map; add O(1), find(t) checks each key k for t−k | O(1) add · O(n) find |
| Subarray Sum Equals K | want a contiguous subarray summing to k | hash prefix sums, not raw values: a subarray sums to k iff two prefixes differ by k | O(n) · O(n) |
| Two Sum Less Than K | largest pair sum strictly < K | sort + two pointers, recording the best sum seen below K | O(n log n) · O(1) |
all of these are "find elements that combine to a target." The decision tree is short: unsorted + exact pair → hash the complement · sorted → two pointers (O(1) space) · k numbers → fix k−2, two-pointer the last two · contiguous → hash prefix sums · maximize under a bound → sort + two pointers. Same idea, five faces.
Group Anagrams Medium
Problem
Given a list of words, bucket together the ones that are anagrams of each other (same letters, any order). Return the groups in any order.
Constraints: up to 10⁴ words, lowercase a–z; total characters up to ~10⁵.
Example 1: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]].
Example 2: ["", "b"] → [[""],["b"]] (empty string has the all-zero signature).
Solution — brute force
Brute force compares each word against every other word by sorting both words or counting letters and checking equality. That can reach O(n²·L log L) time with a visited array, which is correct but wasteful because each group comparison repeats work. The optimized version computes one canonical signature per word and uses it as a hash-map key, so all anagrams land in the same bucket immediately.
List<List<String>> groupAnagramsBrute(String[] strs) {
boolean[] used = new boolean[strs.length];
List<List<String>> ans = new ArrayList<>();
for (int i = 0; i < strs.length; i++) {
if (used[i]) continue;
List<String> group = new ArrayList<>();
for (int j = i; j < strs.length; j++) {
if (!used[j] && sameLetters(strs[i], strs[j])) { used[j] = true; group.add(strs[j]); }
}
ans.add(group);
}
return ans;
}
boolean sameLetters(String a, String b) {
if (a.length() != b.length()) return false;
int[] cnt = new int[26];
for (char c : a.toCharArray()) cnt[c - 'a']++;
for (char c : b.toCharArray()) if (--cnt[c - 'a'] < 0) return false;
return true;
}Brute-force cost: O(n²·L) or O(n²·L log L) depending on the comparison helper, plus output space — too slow for n ≥ 10⁴.
Solution — optimized
Compute one canonical signature per word, then let the hash map gather equal signatures into the same list. This avoids comparing every word pair repeatedly.
Pattern. Canonical-key hashing: map each item to a signature so equivalents collide.
Java.
List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) cnt[c - 'a']++;
StringBuilder key = new StringBuilder();
for (int c : cnt) key.append(c).append('#'); // delimiter avoids 1,11 vs 11,1 collision
groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}Time Complexity
Existing summary: Time O(n·L) · Space O(n·L).
The optimized method is O(n·L) because every character of every word is counted once, and building the 26-count key is constant-size per word for lowercase English letters.
Space Complexity
Space is O(n·L) for the grouped output plus hash keys/lists; each input string is placed into exactly one bucket.
Learning notes
- Why
int[] cnt = new int[26]? — lowercase a–z gives a fixed frequency vector. - Why
c - 'a'? — it maps letters to indices 0 through 25. - Why build a
StringBuilderkey? — arrays do not compare by contents as map keys. - Why append
#delimiter? — it prevents count-collision strings like1,11vs11,1. - Why
computeIfAbsent? — it creates the bucket exactly once.
Anagrams share a canonical form. Use the 26-count signature (O(L)) rather than sorting (O(L log L)) when the alphabet is fixed.
["eat","tea","tan","ate","nat","bat"]. Count-signatures make eat/tea/ate collide, tan/nat collide, bat alone → [[eat,tea,ate],[tan,nat],[bat]].
"I first confirm words are lowercase and group order does not matter. I start with brute force by comparing every pair of words for anagram equality, which is O(n²·L log L) time in the sorting version. I optimize by building one 26-count signature per word and hashing groups by that key, for O(n·L) time and O(n·L) space."
Building the count key without a delimiter collides distinct histograms. Example: counts [1,11] and [11,1] both stringify to "111" and get grouped together. Separate fields — e.g. "1#11" vs "11#1".
"Signature hashing" also powers Group Shifted Strings and isomorphic-string checks.
Same pattern, new tweaks
Same move — "map each item to a canonical key so equivalents collide" — only the definition of "equivalent" changes:
| Variation | "Equivalent" means… | So the key is… |
|---|---|---|
| Group Shifted Strings | same shift pattern ("abc"≡"bcd") | the sequence of gaps between consecutive letters (mod 26) |
| Isomorphic Strings | same structure ("egg"≡"add") | the first-occurrence-position pattern ("egg" → 0,1,1) |
| Find Duplicate File in System | same content | the file's content string |
| Valid Anagram | two strings, not a whole group | compare the two 26-count signatures directly |
Product of Array Except Self Medium
↗ LeetCode: Product of Array Except Self
Problem
Return an array where answer[i] is the product of every element except nums[i] — without using division, in O(n) time.
Constraints: 2 ≤ n ≤ 10⁵; the full product fits in a 32-bit int; division is disallowed (and would break on zeros anyway).
Example 1: nums = [1,2,3,4] → [24,12,8,6] (e.g. position 0 = 2·3·4).
Example 2: nums = [-1,1,0,-3,3] → [0,0,9,0,0] (one zero makes only the zero position nonzero).
Solution — brute force
Brute force builds each answer[i] by multiplying every element except index i. That is O(n²) time and O(1) extra space beyond the output, and division is not allowed anyway. The optimized idea precomputes the product to the left and the product to the right of each index; the Java code stores the left product in the output, then multiplies in a running right product.
int[] productExceptSelfBrute(int[] a) {
int[] out = new int[a.length];
for (int i = 0; i < a.length; i++) {
int product = 1;
for (int j = 0; j < a.length; j++) if (i != j) product *= a[j];
out[i] = product;
}
return out;
}Brute-force cost: O(n²) time, O(1) extra space beyond output — too slow for n ≥ 10⁴.
Solution — optimized
The optimized method splits the answer into left product and right product. It writes all left products into out, then walks from the right multiplying in the product of elements after each index.
Pattern. Prefix × suffix without division.
Java.
int[] productExceptSelf(int[] a) {
int n = a.length; int[] out = new int[n];
out[0] = 1;
for (int i = 1; i < n; i++) out[i] = out[i-1] * a[i-1]; // prefix
int right = 1;
for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= a[i]; } // suffix
return out;
}Time Complexity
Existing summary: Time O(n) · Space O(1) extra (output aside).
The algorithm is O(n) because it performs one left-to-right pass and one right-to-left pass, with constant work per index.
Space Complexity
Extra space is O(1) excluding the required output array: out stores the answer, and right is the only additional running aggregate.
Learning notes
- Why set
out[0] = 1? — there are no elements to the left of index 0. - Why start the prefix loop at
i = 1? —out[i]depends onout[i-1] * a[i-1]. - Why walk from
n - 1down? — that accumulates the product strictly to the right. - Why multiply
out[i] *= rightbeforeright *= a[i]? —a[i]itself must be excluded. - Why no division? — zeros make division unsafe and the prompt disallows it.
answer[i] = (∏ left of i) × (∏ right of i). Two sweeps; carry the running product in the output array to hit O(1) extra space.
After the left sweep, out[i] holds the product of all elements strictly left of i; the right sweep multiplies in the running right product.
[1,2,3,4]. Left-products [1,1,2,6], then multiply each by the running right-product → [24,12,8,6]. Position 0 = 2·3·4, position 3 = 1·2·3.
"I first confirm division is disallowed and zeros may appear, so total-product division is not safe. I start with brute force by multiplying all other entries for every index, which is O(n²) time and O(1) extra space. I optimize with prefix and suffix products in two sweeps, giving O(n) time and O(1) extra space besides the output."
Reaching for division. Example: nums=[1,2,0,4] — dividing the total product by each element blows up at the zero. The prefix/suffix product is division-free and zero-safe.
Prefix/suffix aggregation — the same skeleton as Trapping Rain Water (prefix/suffix max) and candy-distribution problems.
Same pattern, new tweaks
Same skeleton — combine a running result from the left with one from the right — only the aggregate changes:
| Variation | The one thing that changes | So the aggregate is… | Time · Space |
|---|---|---|---|
| Trapping Rain Water | water is bounded by the shorter wall | running max from each side; water = min(L,R) − height | O(n) · O(1) |
| Candy | each child must beat both neighbours | two passes (L→R then R→L), take the max requirement | O(n) · O(n) |
| Maximum Product Subarray | a negative flips sign | track running max and min so a sign-flip can become the new best | O(n) · O(1) |
Longest Consecutive Sequence Medium
↗ LeetCode: Longest Consecutive Sequence
x - 1 is absent; then walking 1→2→3→4 counts each run once instead of restarting inside it.Problem
Given an unsorted array, find the length of the longest run of consecutive integers (like 1,2,3,4) — in O(n), so sorting (O(n log n)) is off the table.
Constraints: 0 ≤ n ≤ 10⁵; values span the full int range; duplicates may appear.
Example 1: nums = [100,4,200,1,3,2] → 4 (the run 1,2,3,4).
Example 2: nums = [] → 0 (no numbers means no run).
Solution — brute force
Brute force can start from every number and repeatedly search the array for the next value x + 1. With a linear search each step, a run like 1..n degenerates to O(n²) time, though it uses only O(1) extra space. Sorting is O(n log n), but the target is O(n), so the optimized set method starts only at true run beginnings and walks each number at most once.
int longestConsecutiveBrute(int[] nums) {
int best = 0;
for (int x : nums) {
int len = 1, cur = x;
while (contains(nums, cur + 1)) { cur++; len++; }
best = Math.max(best, len);
}
return best;
}
boolean contains(int[] nums, int target) {
for (int x : nums) if (x == target) return true;
return false;
}Brute-force cost: O(n²) time with repeated linear searches, O(1) space — too slow for n ≥ 10⁴.
Solution — optimized
The set gives O(1) membership checks, but the real optimization is starting only at sequence beginnings. If x - 1 exists, x belongs to a run that will be counted from an earlier value.
Pattern. Hash set + "only start counting from a sequence's left end."
Java.
int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue; // not a run start
int cur = x, len = 1;
while (set.contains(cur + 1)) { cur++; len++; }
best = Math.max(best, len);
}
return best;
}Time Complexity
Existing summary: Time O(n) · Space O(n).
Expected time is O(n): building the set scans all numbers once, and the inner while walks each consecutive value only when starting from the run boundary.
Space Complexity
Space is O(n) because the hash set stores the distinct input values; duplicates collapse into one set entry.
Learning notes
- Why build a
HashSetfirst? — membership checks become expected O(1). - Why iterate over
set, notnums? — duplicates should not restart the same run. - Why
if (set.contains(x - 1)) continue? — only the left boundary should expand a run. - Why initialize
len = 1? — a run start counts itself. - Why
beststarts at 0? — empty input should return 0.
Put all numbers in a set. A number x begins a run iff x-1 is absent. Only then walk x, x+1, …. Each number is visited at most twice → O(n).
Inner while extends only from true run-starts, so total inner steps ≤ n across the whole outer loop.
[100,4,200,1,3,2]. Only 1 and 100 and 200 are run-starts (their predecessor is absent). From 1 walk 1,2,3,4 → length 4; the others give length 1.
"I first confirm the array is unsorted, duplicates may exist, and the target is the length of the longest consecutive run. I start with brute force by trying to extend a run from every value with repeated searches, which is O(n²) time. I optimize by putting values in a set and expanding only when x - 1 is absent, giving O(n) time and O(n) space."
Omitting the x-1 guard makes it O(n²). Example: nums=[1,2,3,4] — without the guard you walk the run from 1, then from 2, then from 3, then from 4 → 4+3+2+1 steps. Only start from values whose predecessor is absent.
"Start from the boundary" recurs in grid/graph flood-fill and interval merging: identify canonical entry points to avoid redundant work.
Same pattern, new tweaks
Same skeleton — put everything in a set, then only start work from a canonical entry point to avoid redundant re-scans:
| Variation | The one thing that changes | Canonical "start" is… | Time |
|---|---|---|---|
| Longest Consecutive Sequence | 1-D runs of integers | a number x whose predecessor x−1 is absent | O(n) |
| Number of Islands | 2-D grid connectivity | any unvisited land cell (flood it once) | O(R·C) |
| Word Ladder | words linked by 1-letter edits | dedup words in a set so each transform is explored once | O(N·L²) |