Leetcode 219. Contains Duplicate II

Problem Explanation

This problem is asking to return true if there are two indices i and j in the array such that nums[i] equals to nums[j] and the absolute difference between i and j is at most k. If there are no such indices, we should return false.

To illustrate, let's use an example.

Consider an array: nums = [1,2,3,1], and k = 3.

Here, nums[0] = nums[3] = 1 and the absolute difference between 0 and 3 is 3, which matches the condition. Hence we should return true.

Solution Explanation

We will use a hash set (unordered_set in C++, set in Python, HashSet in Java, etc.) and a sliding window approach to solve this problem.

Start by creating a hash set to record the integers in the array. Then, iterate through the array from the beginning. For each iteration, insert the current element into the hash set. If the insertion fails (which means the element already exists in the set), return true. Since we are checking the same element within a window of size k, we need to remove the element that is k distance away from the current element (i.e., nums[i - k]).

Keep repeating this process for all the elements of the array. After traversing through the array, if no duplicate elements are found within the 'k' window, then return false. This approach ensures that we only keep at most 'k' elements in the hash set to avoid unnecessary space usage.

Python Solution

1
2Python
3class Solution:
4    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
5        seen = set()
6        for i in range(len(nums)):
7            if nums[i] in seen:
8                return True
9            seen.add(nums[i])
10            if i >= k:
11                seen.remove(nums[i - k])
12        return False

Java Solution

1
2Java
3class Solution {
4    public boolean containsNearbyDuplicate(int[] nums, int k) {
5        Set<Integer> set = new HashSet<>();
6        for (int i = 0; i < nums.length; i++) {
7            if (!set.add(nums[i])) {
8                return true;
9            }
10            if (i >= k) {
11                set.remove(nums[i - k]);
12            }
13        }
14        return false;
15    }
16}

JavaScript Solution

1
2JavaScript
3var containsNearbyDuplicate = function(nums, k) {
4    let set = new Set();
5    for (let i = 0; i < nums.length; i++) {
6        if (set.has(nums[i])) {
7            return true;
8        }
9        set.add(nums[i]);
10        if (i >= k) {
11            set.delete(nums[i - k]);
12        }
13    }
14    return false;
15};

C++ Solution

1
2C++
3class Solution {
4public:
5    bool containsNearbyDuplicate(vector<int>& nums, int k) {
6        unordered_set<int> seen;
7
8        for (int i = 0; i < nums.size(); ++i) {
9            if (!seen.insert(nums[i]).second)
10                return true;
11            if (i >= k)
12                seen.erase(nums[i - k]);
13        }
14
15        return false;
16    }
17};

C# Solution

1
2C#
3public class Solution {
4    public bool ContainsNearbyDuplicate(int[] nums, int k) {
5        HashSet<int> set = new HashSet<int>();
6        for (int i = 0; i < nums.Length; i++) {
7            if (!set.Add(nums[i])) {
8                return true;
9            }
10            if (i >= k) {
11                set.Remove(nums[i - k]);
12            }
13        }
14        return false;
15    }
16}

In all solutions above, we iterate through the array, at each iteration if the integer already exists in the set we return true. Then we add the integer to the set and remove the integer that is 'k' distance away when 'i' is greater or equal to 'k'. If we successfully traverse through the array without finding any duplicate within the 'k' window, we return false.## Rust Solution

1
2Rust
3use std::collections::HashSet;
4
5pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
6    let mut set = HashSet::new();
7    let k = k as usize;
8    for i in 0..nums.len() {
9        if !set.insert(nums[i]) {
10            return true;
11        }
12        if i >= k {
13            set.remove(&nums[i - k]);
14        }
15    }
16    false
17}

TypeScript Solution

1
2TypeScript
3function containsNearbyDuplicate(nums: number[], k: number): boolean {
4    let set: Set<number> = new Set();
5    for (let i: number = 0; i < nums.length; i++) {
6        if (set.has(nums[i])) {
7            return true;
8        }
9        set.add(nums[i]);
10        if (i >= k) {
11            set.delete(nums[i - k]);
12        }
13    }
14    return false;
15}

Swift Solution

1
2Swift
3class Solution {
4    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
5        var set: Set<Int> = []
6        for i in 0..<nums.count {
7            if set.contains(nums[i]) {
8                return true
9            }
10            set.insert(nums[i])
11            if i >= k {
12                set.remove(nums[i - k])
13            }
14        }
15        return false
16    }
17}

These solutions in Rust, TypeScript and Swift follow the same mechanism. A Set is used to track the unique elements of the array. If a duplicate is found within 'k' positions from the current one, the function returns true. Otherwise, the oldest element is removed from the Set as we are moving forward with the array. If there are no duplicates found, we finally return false at the end of the function.