Contains Duplicate II

EASY✓ CHIP-TIMEDLC #219 — FULL STATEMENT ↗

The drill: Two equal values only count here if they sit close together — at most k positions apart. Decide whether any such near pair exists. The distance rule, not the duplicate hunt, is what shapes the algorithm.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of values and a distance limit k arrive together, and the question is whether any value repeats within k positions of an earlier occurrence of itself.

Two equal values sitting far apart don't count — only pairs whose index gap is k or smaller matter, measured as the absolute distance between their positions.

The answer is a simple yes or no; which pair triggered it, if any, doesn't need to be reported.

EX 01

nums = [5, 2, 5] · k = 2

→ true

PAIR EXACTLY AT DISTANCE K

EX 02

nums = [5, 2, 5] · k = 1

→ false

SAME PAIR, WINDOW ONE TOO SMALL

EX 03

nums = [7, 7] · k = 1

→ true

ADJACENT DUPLICATES

array length runs up to around one hundred thousand elements
the distance limit k is non-negative and can be zero
only pairs of equal values within k positions of each other count
the result reported is a boolean, not the matching pair

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Comparing every pair wastes effort on pairs the distance rule already disqualifies. Which comparisons does each element actually owe?

HINT 2 THE STRUCTURE

Only the previous k elements can ever matter for the current one. Keep exactly those in something that answers “have I seen this value?” instantly.

HINT 3 ONE STEP FROM THE ANSWER

Slide a set of at most k values: check membership, insert the current value, and evict the element that just fell k+1 positions behind. Any hit is your answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ROLLING WINDOWPATTERN · SLIDING WINDOW SETnums = [4, 1, 2, 4, 1] · k = 3

WINDOW (LAST K VALUES)

— empty —

STEP 1

k = 3 — the window remembers only the previous 3 values seen.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/contains-duplicate-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()  # the last k values, at most
        for i, v in enumerate(nums):
            if v in window:
                return True
            window.add(v)
            if len(window) > k:
                window.remove(nums[i - k])
        return False

TIME O(N)SPACE O(K)PYTHON · RACE PACE · 10 LN

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            # only indices within distance k are eligible partners
            for j in range(i + 1, min(i + k, n - 1) + 1):
                if nums[i] == nums[j]:
                    return True
        return False

TIME O(N·K)SPACE O(1)PYTHON · TRAINING PACE · 9 LN

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> window = new HashSet<>(); // the last k values, at most
        for (int i = 0; i < nums.length; i++) {
            if (window.contains(nums[i])) {
                return true;
            }
            window.add(nums[i]);
            if (window.size() > k) {
                window.remove(nums[i - k]);
            }
        }
        return false;
    }
}

TIME O(N)SPACE O(K)JAVA · RACE PACE · 15 LN

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            // only indices within distance k are eligible partners
            for (int j = i + 1; j < nums.length && j <= i + k; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

TIME O(N·K)SPACE O(1)JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED