#219 Contains Duplicate II

frequently reported atNetflix Airbnb Amazon Google Microsoft

the problem

In plain words

Return true if the array holds the same value at two different indices i and j that are at most k apart (|i − j| ≤ k). Otherwise return false.

in nums = [1,2,3,1], k = 3

out true

The two 1s are 3 apart.

in nums = [1,0,1,1], k = 1

out true

Indices 2 and 3.

in nums = [1,2,3,1,2,3], k = 2

out false

Every repeat is 3 apart.

1 ≤ n ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 10⁵

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSliding window (fixed size)Hash lookup (seen before?)

Only the last k values can pair with nums[i]. Keep exactly those in a HashSet — a window of size k that slides one step per index.

solutions

From brute force to optimal

Compare each value with the up-to-k values right after it.

For each i: for j = i + 1 while j < n and j − i ≤ k.
Equal values → true.

timeO(n · min(n, k))

Each of the n indices is compared with at most k later ones.

spaceO(1)

Two loop indices.

javajava.util.*

1class Solution {2    public boolean containsNearbyDuplicate(int[] nums, int k) {3        for (int i = 0; i < nums.length; i++) {4            // only partners at most k steps to the right can count5            for (int j = i + 1; j < nums.length && j - i <= k; j++) {6                if (nums[i] == nums[j]) return true;7            }8        }9        return false;10    }11}

A HashMap from value → latest index; a repeat is close enough if i − last ≤ k.

For each i: prev = map.put(nums[i], i).
If prev != null and i − prev ≤ k → true.

timeO(n) average

One pass with O(1) average HashMap operations.

spaceO(n)

One entry per distinct value in the whole array.

javajava.util.*

1class Solution {2    public boolean containsNearbyDuplicate(int[] nums, int k) {3        Map<Integer, Integer> last = new HashMap<>();   // value -> latest index seen4        for (int i = 0; i < nums.length; i++) {5            Integer prev = last.put(nums[i], i);         // put returns the old index (or null)6            if (prev != null && i - prev <= k) return true;7        }8        return false;9    }10}

The set always holds the values at the last k indices. If the new value is already inside, it is close enough.

For each i: if !set.add(nums[i]) → true.
If set.size() > k: remove nums[i − k], the value that just slid out.

timeO(n) average

Each value is added once and removed once, O(1) on average.

spaceO(min(n, k))

The set never holds more than k + 1 values.

javajava.util.*

1class Solution {2    public boolean containsNearbyDuplicate(int[] nums, int k) {3        Set<Integer> window = new HashSet<>();           // values of the last k indices4        for (int i = 0; i < nums.length; i++) {5            if (!window.add(nums[i])) return true;       // add() is false: it's already in the window6            if (window.size() > k) window.remove(nums[i - k]); // the oldest value slides out7        }8        return false;9    }10}

in the room

How to say it in the interview

talk track

Clarify: |i − j| ≤ k with i ≠ j; k can be 0, and then the answer is always false.
Brute force first: compare each index with the next k — O(n·k), too slow when n = k = 10⁵.
Then: "only the last k values matter" → a HashSet window. Mention the HashMap last-index version as an equally fast answer that uses more memory.

traps

Removing nums[i - k] before checking nums[i]: a copy exactly k apart is thrown out too early and missed.
Shrinking with size() >= k: the window then keeps only k − 1 values.
In the HashMap version, keeping the first index of a value instead of the latest — a later, closer copy is missed.

what they ask next

Follow-ups

Contains Duplicate III (LC 220): the values may differ by at most t?

Keep the window in a TreeSet and ask ceiling(nums[i] − t) — O(n log k). Buckets of width t + 1 bring it to O(n).

What if the numbers arrive as a stream?

The HashSet window already works online — it only ever needs the last k values.

before you submit

Edge cases to test

k = 0: two different indices are never 0 apart → false.
A copy exactly k apart counts (≤ k, not < k).
k bigger than n: the window is everything so far, so any duplicate at all → true.
Values go up to ±10⁹: use them as set keys; never index an array by value.

practise next