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:

Press + to interact
canvasAnimation-image
1 of 11

Let’s look at the code for the algorithm we just discussed.

import java.util.*;
public class Solution {
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (seen.contains(nums[i]))
                return true;
            seen.add(nums[i]);
            if (seen.size() > k)
                seen.remove(nums[i - k]);
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] arrs = {
            {7, 8, 6, 7, 9},
            {-1, 2, -3, 4, -5},
            {900},
            {9, -6, 3, 0, -3, 6, 9},
            {-1000, 1000}
        };
        int[] ks = {3, 5, 1, 6, 10000};
        for (int i = 0; i < arrs.length; i++) {
            System.out.print((i + 1) + ".\tarr: [");
            for (int j = 0; j < arrs[i].length; j++) {
                System.out.print(arrs[i][j]);
                if (j < arrs[i].length - 1)
                    System.out.print(", ");
            }
            System.out.println("]");
            System.out.println("\tk: " + ks[i]);
            System.out.println("\n\tDo duplicates exist? " + (containsNearbyDuplicate(arrs[i], ks[i]) ? "Yes" : "No"));
            System.out.println(String.join("", Collections.nCopies(100, "-")));
        }
    }
}
Contains Duplicate II

Time complexity

The algorithm’s time complexity is O(n)O(n), where nn is the length of the array.

Space complexity

The algorithm’s space complexity is O(min(n,k))O(min(n, k)), which is the space occupied by the set equivalent to the size of the sliding window.

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