LeetCode 219 · Hashing

Contains Duplicate II, explained with a picture

A coat check that only remembers recent guests.

Hashing
▶ Watch it step by step

The problem

Are there two equal numbers whose positions are at most k apart?

Input:  [1, 2, 3, 1, 2, 3], k = 2
Output: false

Picture it

Picture a coat check that only remembers the last k guests. For each guest, look up where their number was last seen; if it was within k positions, answer true.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Dictionary of last positions (or a sliding set of size k). O(n).

Python solution

def contains_nearby(nums, k):
    last = {}                  # value -> last position
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i
    return False

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.