Leetcode 220. Contains Duplicate III

Problem Explanation

Given an array of integers, we need to determine if there are two different indices (i, j) in the array for which the absolute difference of the two numbers at these indices is at most t and the absolute difference of these indices i and j is at most k. If such pair of indices are present, we return True else False.

To better understand the problem, let's look at an example. Given the array nums = [1,2,3,1], k = 3, and t = 0. We need to find distinct indices i and j such that |nums[i] - nums[j]| ≤ t and |i - j| ≤ k. Here, we can see that for i = 0 and j = 3, we have |nums[i] - nums[j]| = 0 ≤ 0 and |i - j| = 3 ≤ 3. So, the function should return true.

Approach

In the solution provided, a balanced tree data structure set is used. It constantly keeps only the k elements occured before the current element. This requires less memory but a bit slower than the bucket solution.

We get the iterator it in the set that is not less than (not smaller than) num[i] - t .This will give us an element which is closest and greater than or equal to num[i] - t. We compare this fetched element with num[i] + t. If this element is smaller than num[i] + t, then it is in the range of the num[i] - t to num[i] + t.

It should be noted that the difference between num[i] and it is in the range of [-t, t].

Python

1
2
3class Solution:
4    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
5
6        window = set()
7        for i in range(len(nums)):
8            num1 = nums[i]
9            if num1 - t in window or num1 + t in window:
10                return True
11            window.add(num1)
12            if len(window) > k:
13                window.remove(nums[i - k])
14        return False

Java

1
2
3public class Solution {
4    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
5        TreeSet<Long> set = new TreeSet<>();
6        for(int i = 0; i < nums.length; ++i){
7            Long s = set.ceiling((long) nums[i] - t);
8            if(s != null && s <= (long) nums[i] + t) return true;
9
10            set.add((long) nums[i]);
11            if(set.size() > k){
12                set.remove((long) nums[i - k]);
13            }
14        }
15        return false;
16    }
17}

Javascript

1
2
3var containsNearbyAlmostDuplicate = function(nums, k, t) {
4     if (nums.length === 0 || k <= 0)
5        return false;
6
7    var set = new Set();
8    
9    for (var i = 0; i < nums.length; i++) {
10        if (set.size > k)
11            set.delete(nums[i - k - 1]);
12
13        for (var num of set) {
14            if (Math.abs(num - nums[i]) <= t)
15                return true;
16        }
17        
18        set.add(nums[i]);
19    }
20    
21    return false;
22};

C++

1
2
3class Solution {
4public:
5    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
6        set<long long> window;
7        for (int i = 0; i < nums.size(); i++) {
8            if (i > k) window.erase(nums[i-k-1]);
9            auto pos = window.lower_bound((long long)nums[i] - t);
10            if (pos != window.end() && *pos - nums[i] <= t) return true;
11            window.insert(nums[i]);
12        }
13        return false;
14    }
15};

C#

1
2
3public class Solution {
4    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
5       SortedSet<long> set = new SortedSet<long>();
6
7        for (int i = 0; i < nums.Length; ++i) {
8            if (set.GetViewBetween((long)nums[i] - t, (long)nums[i] + t).Count > 0) {
9                return true;
10            }
11            set.Add(nums[i]);
12
13            if (i >= k) {
14                set.Remove(nums[i - k]);
15            }
16        }
17        return false;
18    }
19}

It's worth noting that a Set is used to store each num - t and num + t that are in the range k. set.ceiling((long) nums[i] - t) returns the least element that is greater than (long) nums[i] - t (or equals to (long) nums[i] - t)including nums[i]. It will help us to find whether there is a such pair (i, j). If s is not null and s <= (long) nums[i] + t returns true, then we find such pair (i, j) and we return true, otherwise, false.## Conclusion

In summary, the solution to the problem of finding two distinct indices i and j in an array such that |nums[i] - nums[j]| ≤ t and |i - j| ≤ k revolves around the use of the Set data structure. In each of the solutions provided, the implementation algorithm remains essentially the same with only minor syntax distinctions depending on the programming language utilized.

The key here is to constantly maintain a Set window that contains only k elements, making sure to eliminate elements outside this window while traversing the array. By finding an iterator in the Set that is not smaller than nums[i] - t, we can then find an element that is closest and greater or equal to nums[i] - t.

Ultimately, the solution helps to demonstrate that certain data structures like a Set can be quite useful in solving array-related problems as they allow for the efficient addition, removal and search of elements in the array. This approach helps to minimize memory usage while providing a reasonably fast solution to the problem. During actual implementation, developers may choose the most suitable programming language for the task based on their familiarity and the needs of their specific project.