FAANG · LeetCode #49

Group Anagrams — three-stage drill

1The ProblemMedium

Group Anagrams

Group together the strings that are anagrams of one another.

Examples

[eat,tea,tan,ate,nat,bat]→ 3 groups

constraintLowercase letters; anagrams share the same sorted letters.

2The PatternTIME O(n) · SPACE O(n)

Arrays & Hashing

Trade space for time: a hash map turns 'have I seen this?' into an O(1) lookup.

Problems using this pattern

3The SolutionRESULT → 3 groups

Step through it

group words sharing the same sorted letters

Step 1 / 8

Python▎key = sorted letters

1def groupAnagrams(strs):
2    groups = {}
3    for w in strs:
4        key = "".join(sorted(w))
5        groups.setdefault(key, []).append(w)
6    return list(groups.values())

why it worksAnagrams produce the same string once sorted, so the sorted word is a perfect group key. Bucket every word into a hash map keyed by its sorted letters — one pass, O(n·k log k) — and the map's values are the groups.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Group Anagrams — three-stage drill

Group Anagrams

Arrays & Hashing

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent