SyntaxPilot
Courses/DSA and Coding Problems/Lesson 46
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 46 of 90

Hashing deep dive: longest consecutive sequence, group anagrams

queued

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) and contains(x) take O(1) on average (constant time, no matter how many items). It stores each value once, so duplicates disappear.
  • HashMap: like a HashSet, 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 HashMap looks up by. Two keys are "the same" when their equals says so and their hashCodes match.
  • computeIfAbsent(key, k -> new ArrayList<>()): returns the list for key, 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.

  1. 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]]
  1. Valid Anagram (LeetCode 242): are s and t anagrams 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
  1. 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.

  1. Contains Duplicate II (LeetCode 219): is there a pair of equal values whose indices are at most k apart?
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

  1. Why does the HashSet solution run in O(n) even though it has a while loop inside a for loop? The while only runs from the start of a streak, so each number is counted inside at most one streak. Over the whole run the while does at most n steps in total.
  2. 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.
  3. 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.
  4. 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.
  5. Why not use char[] or int[] as a HashMap key in Java? Arrays use identity equals/hashCode; two arrays with the same contents are different keys. Convert them to a String (new String(c), Arrays.toString(count)) or use a List.
  6. 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.
  7. 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), and best must start at 0 for an empty array (bug 3).
  • Group Anagrams: anagrams share a sorted key; a HashMap from 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 HashMap key in Java: arrays compare by identity, so you get one group per word (bug 2). Use a String.

Next episode: Graphs: representation, BFS and DFS.