Contains Duplicate II

Easy Arrays & Hashing Sliding Window · Fixed Original on LeetCode

Contains Duplicate II is a easy arrays & hashing problem solved with the sliding window · fixed pattern. The best approach, optimal (sliding window set), runs in O(n) time and O(min(n, k)) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an integer array nums and an integer k. Return true if there are two different indices i and j with nums[i] == nums[j] and |i - j| <= k, and false otherwise.

In other words: does some value repeat within a distance of at most k positions?

Examples

Example 1

Input
nums = [4, 7, 2, 7, 9], k = 2
Output
true
Why
The two 7s sit at indices 1 and 3, which are 2 apart, and 2 <= k.

Example 2

Input
nums = [5, 1, 8, 5, 3], k = 2
Output
false
Why
The only repeated value is 5, at indices 0 and 3, which are 3 apart: too far.

Example 3

Input
nums = [8, 8, 8], k = 0
Output
false
Why
With k = 0 the two indices would have to be equal, which is not allowed.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n · min(n, k))O(1)
Hash map of last indexO(n)O(n)
Optimal (sliding window set)O(n)O(min(n, k))

1Brute force

TimeO(n · min(n, k))Each element is compared with up to k later elements.
SpaceO(1)Only loop indices.

For each index, compare its value with each of the next k values.

  1. For i from 0 to n - 1, for j from i + 1 to min(n - 1, i + k).
  2. If nums[i] == nums[j], return true.
  3. Return false.
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + k; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

2Hash map of last index

TimeO(n)One pass with O(1) average map operations.
SpaceO(n)The map holds one entry per distinct value, up to n.

Walk left to right and remember, for every value, the last index where it appeared. The closest earlier copy of nums[i] is exactly that last index, so one lookup tells you whether a close-enough pair ends at i.

  1. Create an empty map from value to last index.
  2. For each i: if nums[i] is in the map and i - map[nums[i]] <= k, return true.
  3. Store map[nums[i]] = i (overwriting the older index).
  4. Return false.
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer j = last.get(nums[i]);
            if (j != null && i - j <= k) {
                return true;
            }
            last.put(nums[i], i);
        }
        return false;
    }
}

3Optimal (sliding window set)

TimeO(n)Each value is added once and removed at most once, O(1) on average each.
SpaceO(min(n, k))The set holds at most k + 1 values at any moment.

Keep a set holding exactly the values at the previous k indices. When you reach index i, a valid pair ends at i precisely when nums[i] is already in the set. Then add nums[i] and, if the window has grown past k values, remove the value at index i - k. The set never holds more than k values.

  1. Create an empty set.
  2. For each i: if nums[i] is in the set, return true.
  3. Add nums[i]; if the set now holds more than k values, remove nums[i - k].
  4. Return false.
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> window = new HashSet<>();
        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;
    }
}

Edge cases to test

  • k = 0: the answer is always false
  • k larger than the array: it becomes the plain "any duplicate" question
  • A value that repeats far apart first and close together later, like [1, 2, 3, 1, 1] with k = 1
  • A single element

Hints

Hint 1

When you stand at index i, which earlier positions can still pair with it?

Hint 2

For a repeated value, only its most recent earlier position matters: it is the closest one.

Hint 3

Alternatively keep a set of just the last k values; drop the value that falls out of the window as you move right.

FAQ

What is the best time complexity for Contains Duplicate II?

Optimal (sliding window set) runs in O(n) time and O(min(n, k)) extra space. Each value is added once and removed at most once, O(1) on average each.

Which pattern does Contains Duplicate II use?

It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.

Is there a brute force solution for Contains Duplicate II?

Yes. Brute force takes O(n · min(n, k)) time and O(1) space. For each index, compare its value with each of the next k values.

Which edge cases should I test for Contains Duplicate II?

k = 0: the answer is always false; k larger than the array: it becomes the plain "any duplicate" question; A value that repeats far apart first and close together later, like [1, 2, 3, 1, 1] with k = 1; A single element.