These are the notes for DSA episode 46, a hashing deep dive. Two classic interview problems, and in both of them a HashSet or a HashMap turns a slow answer into a fast one. Problem one, Longest Consecutive Sequence (LeetCode 128): a coding-streak app gets your practice days out of order and must show your longest run of days in a row. Problem two, Group Anagrams (LeetCode 49): a word game puts words made of the same letters into families. For each one we solve it the obvious way first, watch it hit Time Limit Exceeded on a big input, find the key insight, and finish in about O(n) time. Every Java program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), the C++ with g++ -O2 -std=c++17 and the Python with python3, and every output shown is real.
The problem, in real life
Imagine a coding practice app with a streak: it rewards you for practising on days in a row. Your practice days are stored as day numbers, but they arrive from different phones and servers out of order: day 100, 4, 200, 1, 3, 2. The app must show your longest streak. Here days 1, 2, 3 and 4 are in a row, so your longest streak is 4 days. And it must do this for millions of users, so it has to be fast.
The second app is a word game. It wants to show families of words built from the same letters: eat, tea and ate are one family; tan and nat another; bat is alone.
| In the apps | In code |
|---|---|
| Your practice days, shuffled | an int[] array in any order |
| Days in a row (1, 2, 3, 4) | a consecutive sequence |
| Your longest streak | the length of the longest consecutive sequence |
| "Did I practise on day x?" | set.contains(x): a HashSet lookup |
| A family of words with the same letters | a group of anagrams |
| The family's name tag (aet for eat, tea, ate) | a sorted key in a HashMap |
Every word, from zero
- Consecutive: one after another, each one bigger by exactly 1: 3, 4, 5.
- Consecutive sequence (here): a set of such numbers that may sit anywhere in the array, in any order. We return the length of the longest one. Duplicates count once.
- Streak: the real-life name for a run of consecutive days.
- Hashing: turning a value into a number (its hash code) that says which "bucket" to store it in, so we can find it again without searching everything.
HashSet: Java's set built on hashing.add(x)andcontains(x)take O(1) on average (constant time, no matter how many items). It stores each value once, so duplicates disappear.HashMap: like aHashSet, but each key carries a value. Here: key = a sorted word, value = the list of words in that family.- Linear search: checking every element one by one: O(n) per question.
- Anagram: a word with exactly the same letters as another, in a different order: listen ↔ silent, eat ↔ tea ↔ ate.
- Key: the thing a
HashMaplooks up by. Two keys are "the same" when theirequalssays so and theirhashCodes match. computeIfAbsent(key, k -> new ArrayList<>()): returns the list forkey, creating an empty one the first time the key appears.- O(n), O(n log n), O(n²): how the work grows with the input size n (from earlier episodes). For n = 1 lakh: O(n) is about 10^5 steps, O(n²) about 10^10.
Problem 1: Longest Consecutive Sequence (LeetCode 128)
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Your algorithm must run in O(n) time.
| Input | Output | Why |
|---|---|---|
[100, 4, 200, 1, 3, 2] |
4 |
1, 2, 3, 4 |
[0, 3, 7, 2, 5, 8, 4, 6, 0, 1] |
9 |
0 … 8 (the second 0 counts once) |
[] |
0 |
no numbers, no streak |
Constraints: 0 ≤ nums.length ≤ 10^5 (1 lakh), −10^9 ≤ nums[i] ≤ 10^9.
Brute force: count up from every number
For each number x, ask: is x + 1 in the array? Then x + 2? Keep counting until one is missing. And to ask "is it in the array?", loop over the whole array.
import java.util.*;
public class Main {
static boolean has(int[] a, int x) {
for (int v : a) if (v == x) return true;
return false;
}
static int longest(int[] a) {
int best = 0;
for (int x : a) {
int len = 1;
while (has(a, x + len)) len++;
best = Math.max(best, len);
}
return best;
}
public static void main(String[] args) {
System.out.println(longest(new int[]{100, 4, 200, 1, 3, 2}));
System.out.println(longest(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));
}
}
Real output:
4
9
Correct on both LeetCode examples.
1 lakh shuffled days: Time Limit Exceeded
A power user practised for one lakh days in a row, day 0 to day 99,999, and the days arrive shuffled. Replace main with:
int n = 100000;
int[] days = new int[n];
for (int i = 0; i < n; i++) days[i] = i;
Random rnd = new Random(46);
for (int i = n - 1; i > 0; i--) {
int j = rnd.nextInt(i + 1), t = days[i]; days[i] = days[j]; days[j] = t;
}
long t0 = System.nanoTime();
int best = longest(days);
System.out.println("streak " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
(The loop with Random is a Fisher–Yates shuffle: it mixes the array into a random order; seed 46 makes it the same order every run.) Result in the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s, nothing printed).
Why it is slow
- Starting from day 0, we count up a lakh times, and every single lookup scans the whole array of a lakh: 1 lakh × 1 lakh = 10^10 = 1,000 crore steps, from day 0 alone.
- Then day 1 counts up almost as far again, and day 2, and so on. The same streak is counted again and again from its middle. In the worst case that is O(n³).
- Sorting first works. Sort, then walk once: equal neighbours are duplicates, a +1 neighbour extends the streak, anything else starts a new one. That is O(n log n):
static int longest(int[] a) {
if (a.length == 0) return 0;
int[] s = a.clone();
Arrays.sort(s);
int best = 1, len = 1;
for (int i = 1; i < s.length; i++) {
if (s[i] == s[i - 1]) continue; // a duplicate: skip it
if (s[i] == s[i - 1] + 1) len++; // the streak goes on
else len = 1; // a gap: a new streak
best = Math.max(best, len);
}
return best;
}
Real output on the two examples, an empty array and the lakh shuffled days: 4, 9, 0, streak 100000, 195 ms. It passes, but LeetCode asks for O(n), so let's do better.
We need two fixes: (1) a lookup that doesn't scan everything, and (2) stop counting the same streak again from its middle.
The key insight: only start counting at the start of a streak
Picture a railway platform with several trains standing on it, and a list of every coach number.
| On the platform | In code |
|---|---|
| The coach list: check any coach in a second | a HashSet: contains() in O(1) on average |
| A coach with no coach in front of it: the engine end | x - 1 is missing, so a streak starts at x |
| Walk from the first coach to the last, counting | count x + 1, x + 2, … only from a start |
To measure a train you don't start in the middle. Coaches in the middle are never a starting point, so nobody walks the same train twice.
On example one, set = {100, 4, 200, 1, 3, 2}:
| x | Is x − 1 in the set? | What we do |
|---|---|---|
| 1 | 0? No | a streak starts: count 1, 2, 3, 4 (5 is missing) → length 4 |
| 2, 3, 4 | 1, 2, 3? Yes | in the middle of a streak: skip |
| 100 | 99? No | a streak of length 1 |
| 200 | 199? No | a streak of length 1 |
Every number is checked once as a possible start, and counted at most once inside a streak: each number is touched at most twice, so the whole thing is O(n).
The optimal solution in Java
import java.util.*;
public class Main {
static int longest(int[] a) {
Set<Integer> set = new HashSet<>();
for (int x : a) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue;
int len = 1;
while (set.contains(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
public static void main(String[] args) {
System.out.println(longest(new int[]{100, 4, 200, 1, 3, 2}));
System.out.println(longest(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));
System.out.println(longest(new int[]{}));
System.out.println(longest(new int[]{7, 7, 7}));
System.out.println(longest(new int[]{-2, -1, 0, 5, 1}));
}
}
Real output:
4
9
0
1
4
Four and nine for the examples. Zero for the empty array. One for 7, 7, 7 (the set keeps a single 7, so duplicates disappear for free). And four for −2, −1, 0, 1: negative numbers work too. Note that we loop over the set, not the array, so a value that appears many times is only tried once.
1 lakh shuffled days in milliseconds
The same lakh shuffled days that timed out (the main from the brute-force section): real output
streak 100000, 195 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
int longest(const vector<int>& a) {
unordered_set<int> set(a.begin(), a.end());
int best = 0;
for (int x : set) {
if (set.count(x - 1)) continue; // not the start of a streak
int len = 1;
while (set.count(x + len)) len++;
best = max(best, len);
}
return best;
}
int main() {
cout << longest({100, 4, 200, 1, 3, 2}) << "\n";
cout << longest({0, 3, 7, 2, 5, 8, 4, 6, 0, 1}) << "\n";
cout << longest({}) << "\n";
cout << longest({7, 7, 7}) << "\n";
cout << longest({-2, -1, 0, 5, 1}) << "\n";
int n = 100000;
vector<int> days(n);
iota(days.begin(), days.end(), 0);
shuffle(days.begin(), days.end(), mt19937(46));
auto t0 = chrono::steady_clock::now();
int best = longest(days);
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
cout << "streak " << best << ", " << ms << " ms\n";
}
C++'s unordered_set is the hash set; count(x) is 1 if x is there, else 0. iota fills 0, 1, 2, …, and shuffle with mt19937 mixes them. Real output (g++ -O2 -std=c++17):
4
9
0
1
4
streak 100000, 65 ms
The same solution in Python
import random, time
def longest(a):
s = set(a)
best = 0
for x in s:
if x - 1 in s: # not the start of a streak
continue
length = 1
while x + length in s:
length += 1
best = max(best, length)
return best
print(longest([100, 4, 200, 1, 3, 2]))
print(longest([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))
print(longest([]))
print(longest([7, 7, 7]))
print(longest([-2, -1, 0, 5, 1]))
days = list(range(100000))
random.Random(46).shuffle(days)
t0 = time.perf_counter()
best = longest(days)
print(f"streak {best}, {int((time.perf_counter() - t0) * 1000)} ms")
Python's built-in set is a hash set, and x in s is the O(1) average lookup. Real output:
4
9
0
1
4
streak 100000, 23 ms
(Python beat Java here: Java's 195 ms includes boxing every int into an Integer object for the HashSet, and the JIT compiler warming up. Python's set of small integers is very well tuned. All three are far inside the limit.)
Problem 2: Group Anagrams (LeetCode 49)
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
| Input | Output (any order) |
|---|---|
["eat", "tea", "tan", "ate", "nat", "bat"] |
[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]] |
[""] |
[[""]] |
["a"] |
[["a"]] |
Constraints: 1 ≤ strs.length ≤ 10^4 (ten thousand), 0 ≤ strs[i].length ≤ 100, only lowercase English letters. We'll test with twenty thousand words.
Brute force: compare every pair
A helper, same, sorts the letters of both words and compares them. group takes each word not yet used, starts a new group, and compares it with every later word.
import java.util.*;
public class Main {
static boolean same(String a, String b) {
char[] x = a.toCharArray(), y = b.toCharArray();
Arrays.sort(x); Arrays.sort(y);
return Arrays.equals(x, y);
}
static List<List<String>> group(String[] words) {
List<List<String>> res = new ArrayList<>();
boolean[] used = new boolean[words.length];
for (int i = 0; i < words.length; i++) {
if (used[i]) continue;
List<String> g = new ArrayList<>(List.of(words[i]));
for (int j = i + 1; j < words.length; j++)
if (!used[j] && same(words[i], words[j])) { g.add(words[j]); used[j] = true; }
res.add(g);
}
return res;
}
public static void main(String[] args) {
System.out.println(group(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
}
}
Real output:
[[eat, tea, ate], [tan, nat], [bat]]
20,000 random words: Time Limit Exceeded
Random rnd = new Random(46);
String[] words = new String[20000];
for (int i = 0; i < words.length; i++) {
char[] w = new char[6];
for (int k = 0; k < 6; k++) w[k] = (char) ('a' + rnd.nextInt(26));
words[i] = new String(w);
}
long t0 = System.nanoTime();
int groups = group(words).size();
System.out.println(groups + " groups, " + (System.nanoTime() - t0) / 1000000 + " ms");
Twenty thousand random six-letter words. Almost every word is alone, so almost every pair gets compared. Result: Time Limit Exceeded (stopped after 8 s).
Why it is slow
- 20,000 words make about 20,000 × 20,000 / 2 = 20 crore pairs, and every comparison makes two arrays and sorts two words.
- With n words of length k that is O(n² · k log k).
- Each word's sorted letters are recomputed thousands of times, even though they never change.
The key insight: anagrams share a sorted key
Sort the letters of each word:
| Word | Sorted letters (the key) | Group |
|---|---|---|
| eat, tea, ate | aet |
[eat, tea, ate] |
| tan, nat | ant |
[tan, nat] |
| bat | abt |
[bat] |
Anagrams always get the same sorted word, and different families never do. That sorted word is the family's key. Now a HashMap from key to group does all the work: each word computes its key once and joins its group in O(1). No pair is ever compared.
The optimal solution in Java
import java.util.*;
public class Main {
static List<List<String>> group(String[] words) {
Map<String, List<String>> map = new HashMap<>();
for (String w : words) {
char[] c = w.toCharArray();
Arrays.sort(c);
String key = new String(c);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
System.out.println(group(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
System.out.println(group(new String[]{""}));
System.out.println(group(new String[]{"a"}));
System.out.println(group(new String[]{"ab", "ba", "abc", "aab"}));
}
}
Real output:
[[eat, tea, ate], [bat], [tan, nat]]
[[]]
[[a]]
[[ab, ba], [aab], [abc]]
The three families, in HashMap order (a HashMap keeps no particular order, which is fine: LeetCode accepts any order). The empty word sits in its own group: it prints as [[]], empty brackets inside brackets. a is alone. And ab joins ba, while abc and aab stay apart, because their letters differ.
20,000 words in milliseconds
The same twenty thousand random words: real output
19650 groups, 100 ms
Almost twenty thousand groups (nearly every random word is alone), in milliseconds.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> group(const vector<string>& words) {
unordered_map<string, vector<string>> map;
for (const string& w : words) {
string key = w;
sort(key.begin(), key.end()); // anagrams get the same key
map[key].push_back(w); // [] creates an empty group the first time
}
vector<vector<string>> res;
for (auto& [key, g] : map) res.push_back(g);
return res;
}
void print(const vector<vector<string>>& gs) {
cout << "[";
for (size_t i = 0; i < gs.size(); i++) {
cout << (i ? ", " : "") << "[";
for (size_t j = 0; j < gs[i].size(); j++) cout << (j ? ", " : "") << gs[i][j];
cout << "]";
}
cout << "]\n";
}
int main() {
print(group({"eat", "tea", "tan", "ate", "nat", "bat"}));
print(group({""}));
print(group({"a"}));
print(group({"ab", "ba", "abc", "aab"}));
mt19937 rnd(46);
vector<string> words(20000);
for (auto& w : words) { w.resize(6); for (char& c : w) c = 'a' + rnd() % 26; }
auto t0 = chrono::steady_clock::now();
size_t groups = group(words).size();
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
cout << groups << " groups, " << ms << " ms\n";
}
A C++ string can be sorted in place, and map[key] creates an empty vector the first time a key is used (the same job as Java's computeIfAbsent). The random words come from a different generator than Java's, so the group count differs slightly. Real output (g++ -O2 -std=c++17):
[[bat], [tan, nat], [eat, tea, ate]]
[[]]
[[a]]
[[aab], [abc], [ab, ba]]
19688 groups, 16 ms
The same solution in Python
import random, time
from collections import defaultdict
def group(words):
groups = defaultdict(list) # a missing key starts as an empty list
for w in words:
key = "".join(sorted(w)) # anagrams get the same key
groups[key].append(w)
return list(groups.values())
print(group(["eat", "tea", "tan", "ate", "nat", "bat"]))
print(group([""]))
print(group(["a"]))
print(group(["ab", "ba", "abc", "aab"]))
rnd = random.Random(46)
words = ["".join(rnd.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(6)) for _ in range(20000)]
t0 = time.perf_counter()
n = len(group(words))
print(f"{n} groups, {int((time.perf_counter() - t0) * 1000)} ms")
sorted(w) gives a list of letters, and "".join(...) turns it back into a string, which can be a dictionary key. (A tuple, tuple(sorted(w)), works too.) Python dictionaries keep the order in which keys were first added. Real output:
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['']]
[['a']]
[['ab', 'ba'], ['abc'], ['aab']]
19656 groups, 20 ms
Three real bugs
Bug 1: forgetting the start check (counting from every number)
for (int x : set) {
int len = 1; // no "if (set.contains(x - 1)) continue;"
while (set.contains(x + len)) len++;
best = Math.max(best, len);
}
The answers on small inputs stay correct, so this bug is easy to miss. On the lakh shuffled days: Time Limit Exceeded again. Day 0 counts a lakh, day 1 counts almost a lakh, and so on: 1 + 2 + … + 1 lakh ≈ 5 × 10^9 lookups, O(n²) even with a HashSet. The start check is what makes it O(n).
Bug 2: a char[] as the HashMap key
Map<char[], List<String>> map = new HashMap<>();
for (String w : words) {
char[] c = w.toCharArray();
Arrays.sort(c);
map.computeIfAbsent(c, k -> new ArrayList<>()).add(w);
}
Real output on the example:
[[bat], [tea], [ate], [tan], [eat], [nat]]
Six groups, one word each! It compiles and runs without an error, which makes it worse. Arrays don't compare their contents in a HashMap: an array's equals and hashCode are identity based (the same object, not the same letters). Two arrays with the same letters are still two different objects, so every word gets a group of its own (and the order changes from run to run, because identity hash codes do). A tiny check:
char[] x = {'a', 'e', 't'}, y = {'a', 'e', 't'};
System.out.println(x.equals(y)); // false
System.out.println(Arrays.equals(x, y)); // true
System.out.println(new String(x).equals(new String(y))); // true
System.out.println(new String(x).hashCode() == new String(y).hashCode()); // true
Real output: false, true, true, true. Fix: use a String key, new String(c).
Bug 3: best starts at 1
int best = 1; // "every number is a streak of one"
// main: System.out.println(longest(new int[]{}));
Real output:
1
But an empty array has no streak at all; the answer must be 0. Start best at 0: any non-empty input sets it to at least 1 anyway.
Complexity
n = number of items, k = the length of a word.
| Problem | Approach | Time | Extra space | Big input |
|---|---|---|---|---|
| Longest streak | Count up from every x, linear-search lookups | O(n³) worst | O(1) | 1 lakh days: TLE |
| Longest streak | Sort, then one walk | O(n log n) | O(n) for the copy | 1 lakh days: 195 ms |
| Longest streak | Count from every x with a HashSet (bug 1) | O(n²) | O(n) | 1 lakh days: TLE |
| Longest streak | HashSet, count only from a start | O(n) average | O(n) | 1 lakh days: 195 ms (Java) |
| Group anagrams | Compare every pair | O(n² · k log k) | O(n) | 20,000 words: TLE |
| Group anagrams | HashMap, sorted key | O(n · k log k) | O(n · k) | 20,000 words: 100 ms (Java) |
| Group anagrams | HashMap, 26-count key (practice 1) | O(n · k) | O(n · k) |
"Average" because a HashSet lookup is O(1) on average; if many values landed in the same bucket it could be slower, but Java's hash table keeps this rare.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Count up from every x | Time Limit Exceeded | the same streak counted again from its middle: O(n²) | skip x when x - 1 is in the set |
Map<char[], ...> |
[[bat], [tea], [ate], [tan], [eat], [nat]]: 6 groups of one word |
arrays hash and compare by identity | new String(sorted) as the key |
int best = 1 |
1 for an empty array |
no numbers, no streak | start best at 0 |
has(): a loop over the array as the lookup |
Time Limit Exceeded | O(n) per lookup | a HashSet: O(1) on average |
| Compare every pair of words | Time Limit Exceeded | about 20 crore pairs for 20,000 words | one sorted key per word |
Comparing arrays with x.equals(y) |
false for the same letters |
identity, not contents | Arrays.equals(x, y) |
Mini project: the streak board
Build the coding-streak screen for a small class. Store each student's practice days as an int[] (shuffled, with duplicates, from several "devices"). For every student print the longest streak and the days it covered (practice 3), then sort the students by longest streak to make a leaderboard. Extra: also print the current streak, the streak that ends on today's day number (hint: start at today and count down while set.contains(day)). Then add a word-game panel: given the class's favourite words, print every anagram family with more than one word.
Practice
These are the episode's homework items.
- Group anagrams with a 26-count key, in O(n · k).
Solution
Instead of sorting (k log k), count how many times each of the 26 letters appears (k steps). Anagrams have exactly the same counts. Arrays.toString(count) turns the counts into a String such as [1, 0, 0, 0, 1, …], which is a safe HashMap key (an int[] would have bug 2).
import java.util.*;
public class Main {
static List<List<String>> group(String[] words) {
Map<String, List<String>> map = new HashMap<>();
for (String w : words) {
int[] count = new int[26];
for (char ch : w.toCharArray()) count[ch - 'a']++;
String key = Arrays.toString(count);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(map.values());
}
public static void main(String[] args) {
System.out.println(group(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
System.out.println(group(new String[]{"ab", "ba", "abc", "aab"}));
}
}
Real output:
[[eat, tea, ate], [bat], [tan, nat]]
[[ab, ba], [aab], [abc]]
- Valid Anagram (LeetCode 242): are
sandtanagrams of each other?
Solution
Different lengths can never be anagrams. Otherwise add 1 for each letter of s, subtract 1 for each letter of t; they are anagrams exactly when every count ends at 0. O(n) time, O(1) space (26 counters).
public class Main {
static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) if (c != 0) return false;
return true;
}
public static void main(String[] args) {
System.out.println(isAnagram("anagram", "nagaram"));
System.out.println(isAnagram("rat", "car"));
System.out.println(isAnagram("listen", "silent"));
System.out.println(isAnagram("aab", "abb"));
}
}
Real output:
true
false
true
false
- Longest streak: also print the days.
Solution
Remember where the best streak started. The days are then start, start + 1, …, start + best - 1.
import java.util.*;
public class Main {
static List<Integer> longestDays(int[] a) {
Set<Integer> set = new HashSet<>();
for (int x : a) set.add(x);
int best = 0, bestStart = 0;
for (int x : set) {
if (set.contains(x - 1)) continue;
int len = 1;
while (set.contains(x + len)) len++;
if (len > best) { best = len; bestStart = x; }
}
List<Integer> days = new ArrayList<>();
for (int i = 0; i < best; i++) days.add(bestStart + i);
return days;
}
public static void main(String[] args) {
System.out.println(longestDays(new int[]{100, 4, 200, 1, 3, 2}));
System.out.println(longestDays(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));
System.out.println(longestDays(new int[]{}));
}
}
Real output:
[1, 2, 3, 4]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[]
Still O(n): printing the days adds at most n more steps.
- Contains Duplicate II (LeetCode 219): is there a pair of equal values whose indices are at most
kapart?
Solution
A HashMap from value to the last index where we saw it. At each index, if the value was seen before and i - j <= k, answer true; otherwise remember the new index. O(n) time.
import java.util.*;
public class Main {
static boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> last = new HashMap<>(); // value -> last index seen
for (int i = 0; i < nums.length; i++) {
Integer j = last.get(nums[i]);
if (j != null && i - j <= k) return true;
last.put(nums[i], i);
}
return false;
}
public static void main(String[] args) {
System.out.println(containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3));
System.out.println(containsNearbyDuplicate(new int[]{1, 0, 1, 1}, 1));
System.out.println(containsNearbyDuplicate(new int[]{1, 2, 3, 1, 2, 3}, 2));
}
}
Real output:
true
true
false
j is an Integer (not int) so that "never seen" can be null.
Quick quiz
int[] a = {9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6};
longest(a) = ?
Is it 7, 6, 4 or 11?
Answer
7. 3, 4, 5, 6, 7, 8, 9 are all there: 7 numbers. −1, 0, 1 is only 3, because 2 is missing. And the duplicate −1 counts once. Running the optimal longest on this array really prints 7.
Interview questions
- Why does the HashSet solution run in O(n) even though it has a
whileloop inside aforloop? Thewhileonly runs from the start of a streak, so each number is counted inside at most one streak. Over the whole run thewhiledoes at most n steps in total. - Why loop over the set and not the array? With many duplicates (say 1 lakh copies of the start of a long streak), looping over the array would count that streak once per copy: O(n²) again.
- Can you solve Longest Consecutive Sequence without extra space? Sort in place and walk once: O(n log n) time, O(1) extra space (apart from the sort). It trades time for space.
- Why is a sorted word a correct key for anagrams? Two words are anagrams exactly when they have the same letters with the same counts, and sorting writes those letters in one fixed order, so it gives one identical string per family.
- Why not use
char[]orint[]as a HashMap key in Java? Arrays use identityequals/hashCode; two arrays with the same contents are different keys. Convert them to aString(new String(c),Arrays.toString(count)) or use aList. - Sorted key or count key? Sorting costs O(k log k) per word; counting costs O(k) (plus 26 for the key). For long words the count key wins; for short words both are fast.
- What is the worst case of a HashSet lookup? If many values land in the same bucket, a lookup gets slower; Java turns crowded buckets into small balanced trees, so the worst case is O(log n) instead of O(n). On average it is O(1).
Glossary
| Term | Meaning |
|---|---|
| Consecutive | One after another, each bigger by exactly 1 |
| Consecutive sequence | Numbers that form such a run, sitting anywhere in the array in any order |
| Streak | A run of consecutive days (the real-life name) |
| Start of a streak | A number x whose x − 1 is not in the set |
| Duplicate | A value that appears more than once |
| Hashing | Turning a value into a number (its hash code) that picks where it is stored, for fast lookup |
| Hash code | The number hashCode() returns for a value; equal values must have equal hash codes |
| Bucket | One slot of a hash table; values with the same bucket share it |
HashSet |
Java's hash-based set: add / contains in O(1) on average, no duplicates |
HashMap |
Java's hash-based map from keys to values |
unordered_set / unordered_map |
C++'s hash set / hash map |
set / dict / defaultdict |
Python's hash set / hash map / a dict that creates a default value for a missing key |
| Key | What a map looks up by; here the sorted word or the letter counts |
computeIfAbsent |
Returns the value for a key, creating it first if the key is missing |
| Linear search | Checking elements one by one: O(n) per question |
| Anagram | A word with exactly the same letters as another, in a different order |
| Sorted key | A word's letters in alphabetical order (eat → aet); the same for every anagram |
| Count key | The 26 letter counts of a word, as a string |
Identity (equals / hashCode) |
Comparing whether two references are the very same object, not whether their contents match; what Java arrays do |
Arrays.equals |
Compares two arrays element by element |
| Boxing | Wrapping an int in an Integer object so it can go into a HashSet or HashMap |
| Fisher–Yates shuffle | Swapping each position with a random earlier one to mix an array fairly |
| Seed | The starting number of a random generator; the same seed gives the same "random" numbers |
| O(1) average | Constant time per operation on average, independent of n |
| O(n), O(n log n), O(n²), O(n³) | Work that grows linearly / a bit faster than linearly / with the square / with the cube of n |
| k | The length of a word in the complexity of Group Anagrams |
| Lakh / crore | 1 lakh = 100,000 (10^5); 1 crore = 10,000,000 (10^7) |
| Time Limit Exceeded (TLE) | The program was stopped for running too long (8 s in the SyntaxPilot compiler) |
Summary
- Longest Consecutive Sequence: put every number in a
HashSet, and only start counting at a number x whose x − 1 is missing. Each number is touched at most twice: O(n) time, O(n) space. Brute force with linear-search lookups: TLE on 1 lakh days; sorting: O(n log n). - Forgetting the start check is O(n²) even with a
HashSet(bug 1), andbestmust start at 0 for an empty array (bug 3). - Group Anagrams: anagrams share a sorted key; a
HashMapfrom key to group puts every word in its family without comparing pairs: O(n · k log k), or O(n · k) with a 26-count key. Comparing every pair: TLE on 20,000 words. - Never use an array as a
HashMapkey in Java: arrays compare by identity, so you get one group per word (bug 2). Use aString.
Next episode: Graphs: representation, BFS and DFS.