• 19.3%

https://leetcode.com/problems/contains-duplicate-iii/?tab=Description

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

https://discuss.leetcode.com/topic/18453/c-using-set-less-10-lines-with-simple-explanation

C++ using set (less 10 lines), with simple explanation.

https://discuss.leetcode.com/topic/15468/i-finally-got-ac-in-c

I finally got AC in C++

Using a set container to keep the k+1-length array,which all elements are distinct.Before the container’s size reached k+1, we just find the first element that is not less than [nums[i]-t] and judge the element’s value whether it is less than [nums[i]+t]. Starting to move forward by erasing the head and adding element at the backend after the container’s size reached k+1. The existence of the first element ,which is not less than [nums[i]-t] and less than [nums[i]+t], is the prerequisite of existing other eligible elements.

https://discuss.leetcode.com/topic/15172/accept-c-solution

Accept C++ Solution

My idea is to preserve a sliding window containing nearest k numbers, and check if next number collides to the numbers in the window.

#### python

https://discuss.leetcode.com/topic/27608/java-python-one-pass-solution-o-n-time-o-n-space-using-buckets

The idea is like the bucket sort algorithm. Suppose we have consecutive buckets covering the range of nums with each bucket a width of (t+1). If there are two item with difference <= t, one of the two will happen:

For detailed explanation see my blog here

Python

Java

https://discuss.leetcode.com/topic/19991/o-n-python-using-buckets-with-explanation-10-lines

O(n) Python using buckets with explanation, 10 lines.

https://discuss.leetcode.com/topic/15190/python-ordereddict

Python OrderedDict

#### java

https://discuss.leetcode.com/topic/15199/ac-o-n-solution-in-java-using-buckets-with-explanation

AC O(N) solution in Java using buckets with explanation

As a followup question, it naturally also requires maintaining a window of size k. When t == 0, it reduces to the previous question so we just reuse the solution.

Since there is now a constraint on the range of the values of the elements to be considered duplicates, it reminds us of doing a range check which is implemented in tree data structure and would take O(LogN) if a balanced tree structure is used, or doing a bucket check which is constant time. We shall just discuss the idea using bucket here.

Bucketing means we map a range of values to the a bucket. For example, if the bucket size is 3, we consider 0, 1, 2 all map to the same bucket. However, if t == 3, (0, 3) is a considered duplicates but does not map to the same bucket. This is fine since we are checking the buckets immediately before and after as well. So, as a rule of thumb, just make sure the size of the bucket is reasonable such that elements having the same bucket is immediately considered duplicates or duplicates must lie within adjacent buckets. So this actually gives us a range of possible bucket size, i.e. t and t + 1. We just choose it to be t and a bucket mapping to be num / t.

Another complication is that negative ints are allowed. A simple num / t just shrinks everything towards 0. Therefore, we can just reposition every element to start from Integer.MIN_VALUE.

Edits:

Actually, we can use t + 1 as the bucket size to get rid of the case when t == 0. It simplifies the code. The above code is therefore the updated version.

https://discuss.leetcode.com/topic/15191/java-o-n-lg-k-solution

Java O(N lg K) solution

This problem requires to maintain a window of size k of the previous values that can be queried for value ranges. The best data structure to do that is Binary Search Tree. As a result maintaining the tree of size k will result in time complexity O(N lg K). In order to check if there exists any value of range abs(nums[i] - nums[j]) to simple queries can be executed both of time complexity O(lg K)

Here is the whole solution using TreeMap.