Solution: Contains Duplicate II

Let’s solve the Contains Duplicate II problem using the Sliding Window pattern.

We'll cover the following

Statement

You are given an integer array, nums, and an integer k. Determine whether two distinct indices, i and j, are in the array, such that nums[i] == nums[j] and the absolute difference between i and j is at most k. Return TRUE if such indices exist; otherwise, return FALSE.

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3

  • −103≤-10^3 \leq nums[i] ≤103\leq 10^3

  • 0≤0 \leq k ≤104\leq 10^4

Solution

The core intuition of solving this problem is maintaining a sliding window of size k to track elements within a limited range using a set. As we iterate through the array, we check if the current element already exists in the set, indicating a duplicate within the range. If it exists, we return TRUE. Otherwise, the element is added to the set. If the set size exceeds k, we remove the oldest element to ensure that the set only contains elements within the valid range at any time.

Using the above intuition, the solution can be implemented as follows:

  1. Create a set, seen, to track elements within the sliding window of size k.

  2. Loop through each index i of the array nums.

    1. If the current element, nums[i], already exists in the set, a duplicate exists within a range of k indices. Therefore, we return TRUE.

    2. Add the current element to the set.

    3. If the set’s size exceeds k, remove the oldest element in the window (nums[i - k]) to maintain the window’s size. This ensures only elements within the range k are tracked.

  3. If the loop completes without finding duplicates, we return FALSE.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.