(LeetCode) Contains Duplicate III

Question

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Hello!

I am kinda stumped by this question, to be honest. The solutions provided in the (LeetCode) discussion forum for this question did not provide much explanation/thought process as to how to solve it. I'd rather fully understand the technique to solving the problem than having the full implementation code given to me. I feel that it would be the best way to learn.

So, the clue here is to use a (Java) TreeSet to approach this problem. I am assuming that the floor and ceiling methods would be useful here.

I'd appreciate it if there is anyone out there that can give me a bit of a clue/hint to approach this problem. Pseudocode is welcome as well! I don't need the full implementation code as I've said before. Just a starting point would be great! :)

Thanks!

EDIT: I'm also working on this in the meantime! So, if I do eventually get to an answer, I'll post it on here for future reference. :)

Answer 1

The question is quite old, but OP still hasn't posted his/her answer...
I'll try to explain to people who also stumbled on this question.

The following answer is based on buckets and the time complexity is O(n).

The basic idea is to use a sliding window whose width is k. Our attention will be constrained in this window so that the difference between i and j (indices) in this window can not be greater than k. And we check whether there are two numbers in this window with difference at most t. If there are such numbers, then we're done. Otherwise, our window will move forward one step, and we'll check again.

Now the real question is how do we check if there are two such numbers in the window. Of course we can use brutal force, which will be O(K^2), then the whole algorithm will be O(n * K^2). If K is not large, we can accept this.

However, by using buckets, we can do far better!

Whenever we encounter a number in the window, we divide it by (t+1). Suppose the result is B, we then put the number into bucket[B].

If t = 3, then numbers 0, 1, 2, 3 will all be put into bucket[0], numbers 4, 5, 6, 7 will be put into bucket[1] and 8, 9, 10, 11 will be put into bucket[2] and so on. We have guaranteed all numbers in one bucket will have differences not larger than t. And there is still one thing: 4 - 2 = 2 < 3 and they are in different buckets. Yes, some numbers with differences less than t may be put into different buckets. In such cases, however, they can only be in neighboring buckets.

Below is an example:

nums = [1, 5, 17, 6, 8], t = 2, k = 5 

(We don't have to worry about k now since it's the same as the length of nums.)

Since t = 2, so whenever we encounter a number in the list, we divide it by t+1 (integer divide is used) and put it in corresponding bucket.

1 / 3 = 0   -->   We put 1 in bucket[0]

5 / 3 = 1   -->   We put 5 in bucket[1]

Since there may be elements in buckets neighboring bucket[1] satisfying the requirements, we need to check this. bucket[0] has number 1, but 5 - 1 > 3 and there's no bucket[2] yet, so we carry on.

17 / 3 = 5   -->   We put 17 in bucket[5]

There's no bucket[4] or bucket[6], so we carry on.

6 / 3 = 2   -->   We put 6 in bucket[2]

We have to check number in bucket[1]: |5 - 6| = 1 < 2 so there are such numbers and we return True.

If we continue to put 8 in bucket[2] we'll find there already is an element in it, which is 6. Since all elements in one bucket have differences not larger that t, we are done.

So to check if there are two numbers with differences less than t, we put every number we encounter in a bucket. If there is already an element in that bucket, then we're done. Otherwise, we check if neighboring buckets have element satisfying the requirement, if there isn't, we continue to put numbers into bucket.

We're almost finished. Now we need to consider the window width k. After putting all k numbers into buckets, if we haven't find two such numbers, we need to move the window one step forward. That is to say, to delete the leftmost number and its corresponding bucket and add a new number into its bucket. If its bucket has already been taken, then we're done. Otherwise we check its neighboring buckets, if it has any.

Below is my Python code.

if t < 0 or not nums or k <= 0:
    return False
buckets = {}
width = t + 1

for n, i in enumerate(nums):
    buck = i // width
    if buck in buckets:
        return True
    else:
        buckets[buck] = i
        if buck - 1 in buckets and i - buckets[buck-1] <= t:
            return True
        if buck + 1 in buckets and buckets[buck+1] - i <= t:
            return True
        if n >= k:
            del buckets[nums[n-k] // width]
return False

Answer 2

The optimal soluiton O(n) can be done as @Jing Zhao explained. However in Java you have to take care of other things, such as integer overflow.

This is my solution in java:

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (nums == null || k < 0 || t < 0) return false;
    Map<Integer, Integer> buckets = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int bucket = (int) Math.floorDiv(nums[i], (long) t + 1);
        if (buckets.containsKey(bucket)) return true;
        else {
            buckets.put(bucket, nums[i]);
            // Cast to long as it overflows if 2147483647 - (-1) => -2147483648
            if (buckets.containsKey(bucket - 1) && nums[i] - (long) buckets.get(bucket - 1) <= t) return true;
            if (buckets.containsKey(bucket + 1) && buckets.get(bucket + 1) - (long) nums[i] <= t) return true;
            if (buckets.size() > k) {
                buckets.remove((int) Math.floorDiv(nums[i - k], (long) t + 1));
            }
        }
    }
    return false;
}

First of all you have to handle negative buckets. For example if nums[i] = -1 and t = 2:

int bucket0 = -1/3 = 0 // Remember to divide by (t+1) 

This is not ok, as it would place another number for example nums[i] = 2 in bucket "0" as well and it would return true as they are in the same bucket. But the distance between -1 and 2 is 3 and not 2! So it should return false. The correct way to handle this is to use Math.floorDiv :

int bucket1 = Math.floorDiv(-1,3) = -1

This would place -1 in bucket "-1" and should work fine. For negative numbers the buckets change a little bit. This was hard for me to understand, so I try to explain it in more detail.

First, the reason why we divide by (t+1) and not just "t" is the following: Assume t = 2, and if just divide by "t" then you can have in bucket "1":

2,3 // Because 2/2 and 3/2 give "1"

But this bucket only accounts for a difference of "1" instead of "2", for example, 4 should also be included as 4 - 2 is 2. Now if we divide by (t+1):

3/3,4/3,5/3 // Because all those divisions yield "1"

With this, we are sure that all values within a distance of "t", in this case 2, lie within the same bucket.

We can see that the bucket contains all values starting from the exact division, in this case 3/3, the next bucket "2", will start with 6/3. But in case of negatives numbers they will start at one number more from the exact division. This is because 0 is included in bucket 0.

bucket with "1" => 3,4,5
bucket with "0" => 0,1,2
bucket with "-1" => -1,-2,-3
bucket with "-2" => -4,-5,-6

If we use regular int division in Java for -1, we would get:

-1/3 = 0 // This would go to bucket "0"
-2/3 = 0 // This would go to bucket "0"

This is because regular int division in Java only truncates, so if you get a value of 0.xxxx it would be truncated to just 0 or if you have -1.XXX it would be truncated with -1. But with Math.floorDiv, the division will get the actual floor of the value so with a negative value of -1.xxxx you will get -2, and for -1/3 if would be -1.

Hope this can help someone with this problem. The solution is very clever and you have to handle many different edge cases.

Answer 3

First implementation that comes to mind is just two for loops, with one nested.

Within the inner for loop check the logic for abs(nums[i]-nums[j]) <= t and abs(i-j)<=k.

Outer loop: i from 0 to n

Inner loop: j from i+1 to n