Arrays

Episode 12 First Missing Positive

6 min · LeetCode 41 · Java

Title card of Episode 12: First Missing Positive

▶ This video is coming to YouTube soon.

LeetCode 41, First Missing Positive, solved on screen. Three examples show the cases: every number from 1 up is there, there's a gap in the middle, and 1 itself is missing. A HashSet solves it in O(n) time, but the problem allows only O(1) extra memory. So we use the array itself as the set: swap every value v into slot v − 1, then the first slot i that doesn't hold i + 1 gives the answer. O(n) time, O(1) space.

What you'll learn

  • What First Missing Positive asks, through three worked examples
  • The HashSet solution: O(n) time, but O(n) space
  • The key idea: the answer is always between 1 and n + 1
  • Cyclic placement: swap every value into its own seat, in place
  • Why the swaps add up to O(n), even with a loop inside a loop

Chapters

  1. 0:00The problem
  2. 0:17Examples
  3. 0:57HashSet check, visualized
  4. 1:26HashSet check: the code
  5. 1:41HashSet check, line by line
  6. 2:16Swap into place: the idea
  7. 2:37Swap into place, visualized
  8. 3:41Swap into place: the code
  9. 3:57Swap into place, line by line
  10. 5:05Comparing the approaches