Arrays

Episode 4 Contains Duplicate II

6 min · LeetCode 219 · Java

Title card of Episode 4: Contains Duplicate II

▶ This video is coming to YouTube soon.

LeetCode 219, Contains Duplicate II, solved on screen. Three examples show what counts: two copies exactly k apart, a close pair after one that's too far, and an array where every number repeats but never close enough. Then we watch the brute force compare each number with the next k, read its code line by line, and see why it's O(n · k). Finally, a sliding window keeps only the last k numbers in a HashSet and answers in one O(n) pass.

What you'll learn

  • What Contains Duplicate II asks, through three worked examples
  • The brute force: compare with the next k, O(n · k) time, O(1) space
  • The key idea: only the last k numbers can be close enough
  • The sliding window HashSet: O(n) time, O(k) space
  • Why the window drops nums[i − k − 1] before each add

Chapters

  1. 0:00The problem
  2. 0:15Examples
  3. 0:58Brute force, visualized
  4. 1:57Brute force: the code
  5. 2:13Brute force, line by line
  6. 2:56Sliding window: the idea
  7. 3:16Sliding window, visualized
  8. 4:17Sliding window: the code
  9. 4:34Sliding window, line by line
  10. 5:21Comparing the approaches