Arrays & Hashing · 164Easy
Contains Duplicate II
Given an integer array nums and an integer k, return true if there are two DISTINCT indices i and j such that nums[i] == nums[j] and |i - j| <= k.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5
Examples
containsNearbyDuplicate([1, 2, 3, 1], 3) -> true containsNearbyDuplicate([1, 0, 1, 1], 1) -> true containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2) -> false // duplicates exist, but too far apart containsNearbyDuplicate([1, 1], 1) -> true // adjacent duplicates containsNearbyDuplicate([1, 1], 0) -> false // k = 0 can never succeed containsNearbyDuplicate([1, 2, 3, 1], 10) -> true // k larger than the array
Edge cases
- k = 0 can never succeed — the indices must be distinct.
- k larger than the array length behaves like plain Contains Duplicate.
Show the target complexity (spoiler)
- Naive
- O(n * k) time — for every index, scan the next k elements.
- Target
- O(n) time, O(min(n, k)) space — a sliding-window Set of the last k values (or a map of value -> last index seen).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/164-contains-duplicate-ii.js ./practice c 164