Arrays

Episode 11 Longest Consecutive Sequence

6 min · LeetCode 128 · Java

Title card of Episode 11: Longest Consecutive Sequence

▶ This video is coming to YouTube soon.

LeetCode 128, Longest Consecutive Sequence, solved on screen. Three examples show what counts as a run: order in the array doesn't matter, a repeat counts once, and consecutive means exactly +1. Sorting puts every run side by side, so one scan finds the longest, but the sort costs O(n log n). Then a HashSet does it in O(n): only start counting at numbers with no x − 1 before them, so every number is counted once.

What you'll learn

  • What counts as a consecutive run, through three worked examples
  • Sort and scan: O(n log n) time, O(1) extra space
  • The key idea: a run starts at x only when x − 1 is missing
  • The HashSet solution: O(n) time, O(n) space
  • Why a while loop inside a for loop is still O(n) here

Chapters

  1. 0:00The problem
  2. 0:18Examples
  3. 1:00Sort and scan, visualized
  4. 1:54Sort and scan: the code
  5. 2:08Sort and scan, line by line
  6. 3:03Count from starts: the idea
  7. 3:22Count from starts, visualized
  8. 4:27Count from starts: the code
  9. 4:43Count from starts, line by line
  10. 5:39Comparing the approaches