Arrays

Episode 9 Roman to Integer

6 min · LeetCode 13 · Java

Title card of Episode 9: Roman to Integer

▶ This video is coming to YouTube soon.

LeetCode 13, Roman to Integer, solved on screen. Three examples show the one rule that matters: VI is 6 but IV is 4, because a smaller symbol just before a bigger one is subtracted. The brute force tries a table of all 13 symbols, pairs like CM and IV first, at every position; we watch it search, read its code line by line, and see why the table's order matters. Then one pass with a map of the 7 values needs a single comparison per letter: subtract a symbol when it's smaller than the next one, otherwise add it.

What you'll learn

  • How Roman numerals add and subtract, through three worked examples
  • The brute force: all 13 symbols, pairs first, O(n) with a big constant
  • Why the two-letter symbols have to be tried before single letters
  • The one-pass solution: compare each symbol with the next, O(n) time, O(1) space
  • Why the last symbol is always added

Chapters

  1. 0:00The problem
  2. 0:15Examples
  3. 0:52Brute force, visualized
  4. 1:49Brute force: the code
  5. 2:09Brute force, line by line
  6. 3:04One pass with a map: the idea
  7. 3:22One pass with a map, visualized
  8. 4:10One pass with a map: the code
  9. 4:23One pass with a map, line by line
  10. 5:15Comparing the approaches