Arrays

Episode 10 Verify an Alien Dictionary

6 min · LeetCode 953 · Java

Title card of Episode 10: Verify an Alien Dictionary

▶ This video is coming to YouTube soon.

LeetCode 953, Verify an Alien Dictionary, solved on screen. Three examples cover every case: the first letters decide, a later letter decides, and the prefix trap (apple before app is not sorted). The brute force compares every pair of words, finding each letter with indexOf; we watch it work, read its code line by line, and see why it's O(n²·L). Then a rank table built once turns each lookup into one array access, and because order carries over from neighbour to neighbour, comparing adjacent words is enough: O(n·L).

What you'll learn

  • What sorted means in an alien alphabet, through three worked examples
  • The prefix case: why apple before app is out of order
  • The brute force: every pair of words with indexOf, O(n²·L) time
  • The rank table: each letter's position in one array lookup
  • Why checking neighbours is enough: O(n·L) time, O(1) space

Chapters

  1. 0:00The problem
  2. 0:16Examples
  3. 0:56Brute force, visualized
  4. 1:50Brute force: the code
  5. 2:09Brute force, line by line
  6. 3:01Rank table: the idea
  7. 3:22Rank table, visualized
  8. 4:11Rank table: the code
  9. 4:28Rank table, line by line
  10. 5:09Comparing the approaches