Contains Duplicate II

NeetCode: Contains Duplicate II · LeetCode: 219. Contains Duplicate II · Difficulty: Easy

Given an integer array nums and an integer k, return true if there are two distinct indices i and j with nums[i] == nums[j] and |i - j| <= k.

Example

Text

Input:  nums = [1, 2, 3, 1], k = 3          Output: true
Input:  nums = [1, 0, 1, 1], k = 1          Output: true
Input:  nums = [1, 2, 3, 1, 2, 3], k = 2    Output: false

Brute force: compare each element with the next k

For every index i, look at the following k elements and check for an equal value. That is n starting points times up to k comparisons. The bound i + k + 1 is computed in long so a large k cannot overflow int.

Java

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            int end = (int) Math.min((long) i + k + 1, nums.length);
            for (int j = i + 1; j < end; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsNearbyDuplicate(new int[] {1, 2, 3, 1}, 3));
        System.out.println(s.containsNearbyDuplicate(new int[] {1, 0, 1, 1}, 1));
        System.out.println(s.containsNearbyDuplicate(new int[] {1, 2, 3, 1, 2, 3}, 2));
        System.out.println(s.containsNearbyDuplicate(new int[] {}, 5));
        System.out.println(s.containsNearbyDuplicate(new int[] {7, 7}, 0));
    }
}

Output

true
true
false
false
false

Time: O(n * min(n, k)). Space: O(1).

Optimal: hash set as a window of the last k elements

A duplicate is "close" exactly when both copies fit in a window of k + 1 consecutive elements. Slide such a window along the array and keep its contents in a HashSet<Integer>. Set.add returns false when the value is already present. Before inserting nums[i], ask whether it is already in the set: if so, the earlier copy is at most k positions back. After inserting, if the window has grown beyond k elements, remove the element that just fell off the left edge, nums[i - k].

With k = 0 the window is emptied immediately, so nothing matches, which is correct because the indices must be distinct.

Java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> window = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!window.add(nums[i])) {
                return true;
            }
            if (window.size() > k) {
                window.remove(nums[i - k]);
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsNearbyDuplicate(new int[] {1, 2, 3, 1}, 3));
        System.out.println(s.containsNearbyDuplicate(new int[] {1, 0, 1, 1}, 1));
        System.out.println(s.containsNearbyDuplicate(new int[] {1, 2, 3, 1, 2, 3}, 2));
        System.out.println(s.containsNearbyDuplicate(new int[] {}, 5));
        System.out.println(s.containsNearbyDuplicate(new int[] {7, 7}, 0));
    }
}

Output

true
true
false
false
false

Time: O(n) expected. Space: O(min(n, k)).

window.size() > k implies i >= k, because the window holds at most i + 1 elements, so nums[i - k] is a valid index. window.remove(nums[i - k]) on a Set<Integer> removes by value, because the int argument is boxed to Integer.