VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 02: Hashing

Lesson 2.2 of 12 in this moduleFree

Contains Duplicate

Does any value appear twice? From comparing every pair, to sorting and checking neighbours, to one pass with a hash set. Then duplicates within k positions, near-duplicates within a tolerance, small integer ranges and deduplicating training data at scale.

about 10 min 5 Python examples 2 quick checks

Problem. Return True if any value appears at least twice in nums, otherwise False.

text
[1, 2, 3, 1]   →   True
[1, 2, 3, 4]   →   False

ML context. Duplicate detection is a data-quality step in every pipeline: the same example in the training and test sets leaks the answer and inflates your metrics. Deduplicating user ids, image hashes or document fingerprints is this problem at scale, and its variants (duplicates within a time window, near-duplicates within a tolerance) are the ones you'll meet in practice.


1. Step 1: Clarify

Question Answer Why it matters
n? Up to 10⁵ O(n²) = 10¹⁰: too slow
Values? Any integers (−10⁹ to 10⁹) Too wide for a plain boolean array
Extra memory allowed? Yes (ask!) Decides set versus sort
Can I modify the input? Maybe Sorting in place needs it
Return early? Yes, at the first repeat Best case becomes O(1)

2. Step 2: Brute force: compare every pair

python
def contains_duplicate_brute(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False


assert contains_duplicate_brute([1, 2, 3, 1])
assert not contains_duplicate_brute([1, 2, 3, 4])
assert not contains_duplicate_brute([])
print("brute force works: O(n²) time, O(1) space")

O(n²) time, O(1) space. At n = 10⁵: about 5 × 10⁹ comparisons. Too slow.


3. Step 3: Optimise

The waste: each new value is compared against every earlier value one at a time. Two ways to fix it: bring equal values together (sorting), or remember the earlier values in a structure with O(1) lookup (hashing).

Optimisation A: sort, then compare neighbours

After sorting, equal values sit next to each other, so one pass over adjacent pairs finds any duplicate.

python
def contains_duplicate_sort(nums):
    nums = sorted(nums)                         # O(n log n); sort in place if allowed
    return any(nums[i] == nums[i + 1] for i in range(len(nums) - 1))


assert contains_duplicate_sort([1, 2, 3, 1])
assert not contains_duplicate_sort([1, 2, 3, 4])
print("sort version: O(n log n) time, O(1) extra if sorted in place")

O(n log n) time; O(1) extra memory if you may sort in place (nums.sort()), otherwise O(n) for the copy.

Optimisation B: one pass with a hash set

Keep a set of values seen so far. For each value: if it's already in the set, we found a duplicate; otherwise add it.

frames over [1, 2, 3, 1]; the seen set grows to {1, 2, 3}, and at index 3 the value 1 is already in the set, so the answer is True and the scan stops.
Diagram— frames over [1, 2, 3, 1]; the seen set grows to {1, 2, 3}, and at index 3 the value 1 is already in the set, so the answer is True and the scan stops.
python
import random


def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:                 # O(1) average
            return True               # stop at the first repeat
        seen.add(x)
    return False


def brute(nums):
    return any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, len(nums)))


rng = random.Random(36)
for _ in range(1000):
    nums = [rng.randint(-20, 20) for _ in range(rng.randint(0, 12))]
    assert contains_duplicate(nums) == brute(nums)
assert len(set([1, 2, 3, 1])) < 4                 # the one-liner: correct, but never stops early
print("hash set: O(n) time, O(n) space, matches brute force on 1,000 cases")
  • Time: O(n) average, and it stops early at the first repeat.
  • Space: O(n) for the set.
  • The one-liner len(set(nums)) < len(nums) is also O(n), but always builds the whole set. On a stream with an early duplicate, the loop wins.

Quick check

Sorting uses O(1) extra memory and hashing uses O(n). When is sorting the better choice?

  1. Never
  2. When memory is the binding constraint and you may modify the input: O(n log n) time but no extra set
  3. When n is large
  4. When values are strings
Show the answer

B. When memory is the binding constraint and you may modify the input: O(n log n) time but no extra set — It's a time-for-memory trade: the hash set is faster but needs O(n) extra memory.


4. When the constraints change

a decision map: sort and compare neighbours with no extra memory, a hash set for the classic case, a bit array for a small integer range, a sliding-window set for duplicates within k positions, and a Bloom filter for billions of items.
Diagram— a decision map: sort and compare neighbours with no extra memory, a hash set for the classic case, a bit array for a small integer range, a sliding-window set for duplicates within k positions, and a Bloom filter for billions of items.

Change A: duplicates only count within k positions

"Is there i ≠ j with nums[i] == nums[j] and |i − j| ≤ k?" Keep a set of only the last k values: add each new value, and remove the one that falls out of the window. O(n) time, O(k) space.

python
import random


def duplicate_within_k(nums, k):
    window = set()
    for i, x in enumerate(nums):
        if x in window:
            return True
        window.add(x)
        if len(window) > k:
            window.remove(nums[i - k])          # value now more than k positions back
    return False


def brute_k(nums, k):
    return any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, min(len(nums), i + k + 1)))


assert duplicate_within_k([1, 2, 3, 1], 3)
assert not duplicate_within_k([1, 2, 3, 1, 2, 3], 2)
rng = random.Random(37)
for _ in range(1000):
    nums = [rng.randint(0, 6) for _ in range(rng.randint(0, 12))]
    k = rng.randint(0, 5)
    assert duplicate_within_k(nums, k) == brute_k(nums, k)
print("sliding-window set: O(n) time, O(k) space")

ML version: "has this user sent the same request in the last 1,000 events?"

Change B: near-duplicates (values within t of each other, within k positions)

Exact hashing can't find "close" values. Bucket by value: put x in bucket x // (t + 1). Two values within t are either in the same bucket or in neighbouring ones, so check three buckets. Still O(n) time, O(k) space.

python
import random


def near_duplicate(nums, k, t):
    width = t + 1
    buckets = {}
    for i, x in enumerate(nums):
        b = x // width
        if b in buckets:
            return True                                     # same bucket ⇒ within t
        for nb in (b - 1, b + 1):
            if nb in buckets and abs(x - buckets[nb]) <= t:
                return True
        buckets[b] = x
        if i >= k:
            del buckets[nums[i - k] // width]               # keep only the last k values
    return False


def brute_near(nums, k, t):
    return any(abs(nums[i] - nums[j]) <= t
               for i in range(len(nums)) for j in range(i + 1, min(len(nums), i + k + 1)))


rng = random.Random(38)
for _ in range(1000):
    nums = [rng.randint(-30, 30) for _ in range(rng.randint(0, 12))]
    k, t = rng.randint(1, 5), rng.randint(0, 6)
    assert near_duplicate(nums, k, t) == brute_near(nums, k, t)
print("bucketing finds near-duplicates in O(n)")

Bucketing by a quantised value is the same idea as locality-sensitive hashing, used to find near-duplicate documents and images: similar items are hashed to the same bucket on purpose.

Change C: small integer range, or billions of items

  • Values in 0..R with small R: a boolean array (or a bit array) replaces the set: O(n + R) time, R bits, no hashing.
  • Billions of items: a set of 10⁹ ids needs tens of gigabytes. A Bloom filter answers "definitely new" or "probably seen" with about 10 bits per item and a tunable false-positive rate. Data pipelines use one to skip most exact checks.

The full table

If the constraint becomes… Best approach Time Space
O(1) extra memory, may sort Sort, compare neighbours O(n log n) O(1)
Classic Hash set, stop early O(n) O(n)
Values in a small range R Boolean / bit array O(n + R) O(R)
Within k positions Sliding-window set O(n) O(k)
Within value t and k positions Buckets of width t + 1 O(n) O(k)
Billions of items Bloom filter (+ exact check on "maybe") O(n) ~10 bits per item
Near-duplicate documents / images Locality-sensitive hashing ~O(n) O(n) signatures

Quick check

Why does bucketing by x // (t + 1) find values within t of each other with only three bucket checks?

  1. Two values within t can't be more than one bucket apart, so checking the value's own bucket and its two neighbours covers every possible match
  2. Because the array is sorted
  3. Because buckets are sets
  4. It only works for t = 0
Show the answer

A. Two values within t can't be more than one bucket apart, so checking the value's own bucket and its two neighbours covers every possible match — Bucket width t + 1 guarantees close values land in the same or an adjacent bucket.


5. Saying it out loud

"Comparing every pair is O(n²). Sorting brings equal values together: O(n log n) with O(1) extra if I can sort in place. With memory available, I'd keep a set of seen values and return at the first repeat: O(n) time, O(n) space. If duplicates only count within k positions, the set holds just the last k values; for near-duplicates I'd bucket by value."


Check yourself

  1. What's the waste in the brute force, and what are the two ways to remove it?
  2. Compare the sort and set versions in time and memory.
  3. Why can the loop beat len(set(nums)) < len(nums)?
  4. How does the window version keep memory at O(k)?
  5. Why do near-duplicates need three bucket checks?
  6. What would you use for a billion ids, and what does it give up?
Answers
  1. Each value is compared against all earlier ones individually; fix it by sorting (equal values adjacent) or by a set (O(1) membership).
  2. Sort: O(n log n) time, O(1) extra if in place. Set: O(n) time, O(n) extra.
  3. It stops at the first repeat; the one-liner always processes everything.
  4. It removes the value k positions back each step, so the set never holds more than k values.
  5. Values within t are in the same bucket or an adjacent one (width t + 1).
  6. A Bloom filter: ~10 bits per id, but it can say "probably seen" for a new id (false positives), so confirm those exactly if needed.