Arrays

Episode 6 Group Anagrams

6 min · LeetCode 49 · Java

Title card of Episode 6: Group Anagrams

▶ This video is coming to YouTube soon.

LeetCode 49, Group Anagrams, solved on screen. We start with three examples, including the empty string. Then we watch the brute force check every word against every group so far, read its code line by line, and see why it's O(n²·k). Finally, the trick that makes it one pass: anagrams sort to the same string, so that sorted string becomes a HashMap key, and each word drops straight into its group in O(n·k log k).

What you'll learn

  • What Group Anagrams asks, through three worked examples
  • The brute force: check every group, O(n²·k) time
  • The key idea: anagrams sort to the same string
  • The sorted-key HashMap solution: O(n·k log k) time, O(n·k) space
  • How a 26-count key makes it O(n·k)

Chapters

  1. 0:00The problem
  2. 0:16Examples
  3. 0:50Brute force, visualized
  4. 1:50Brute force: the code
  5. 2:06Brute force, line by line
  6. 2:55Sorted-key HashMap: the idea
  7. 3:13Sorted-key HashMap, visualized
  8. 4:23Sorted-key HashMap: the code
  9. 4:43Sorted-key HashMap, line by line
  10. 5:23Comparing the approaches