# [LeetCode] Contains Duplicate III

Problem Statement

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.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0

Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2

Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3

Output: false

Basic Idea

Two requirements

The absolute difference between nums[i] and nums[j] is at most t.

The absolute difference between i and j is at most k.

Solution

The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk).

We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which maintains a sliding window. So when we insert an element to the treeSet and the index is now greater than or equal to k, we need to slide the window by 1 by removing the first element (in the window) from the treeset.

So the basic idea is for each element nums[i], we check if there is any element between [nums[i] — t, nums[i] + t]. If yes, return true.

**class** Solution {

boolean **containsNearbyAlmostDuplicate**(int[] nums, int k, int t) {

int n=nums.length;

TreeSet<**Integer**> set = new TreeSet<>();

for(int i=0; i< n;i++){

Integer floor = set.floor(nums[i]+t);

Integer ceiling = set.ceiling(nums[i]-t);

if((**floor!=null **&& floor>=nums[i]) || (**ceiling!=null** && ceiling<=nums[i])){

return *true*;

}

set.add(nums[i]);

if(i>=k){

set.remove(nums[i-k]);

}

}

return *false*;

}

}

Example 4:

[-2147483648,-2147483647],

k = 3, t = 3For the scenarios involving minimum(-2147483648) or maximum(

2147483647) Integer values as elements in the array, using a TreeSet with generic type‘Integer’can causeOverflow or Underflow.

A simple fix, to handle the underflow or overflow, is to use a *different data type. *If we want to allow values larger than *2147483647* (or smaller than *-2147483648*), we can simply use the *long* data type or a *BigInteger* instead.

Though variables of type *long* can also overflow, the minimum and maximum values are much larger and are probably sufficient in most situations.

The value range of *BigInteger* is not restricted, except by the amount of memory available to the JVM.

So, here, we are going to use ‘Long’ as the data type of the TreeSet elements.

**class** FixedSolution {

boolean **containsNearbyAlmostDuplicate**(int[] nums, int k, int t) {

int n=nums.length;

TreeSet<**Long**> set = new TreeSet<>();

for(int i=0; i< n;i++){

Long floor = set.floor((long)nums[i]+t);

Long ceiling = set.ceiling((long)nums[i]-t);

if((**floor!=null** && floor>=nums[i]) || (**ceiling!=null** && ceiling<=nums[i])){

return **true**;

}

set.add((long)nums[i]);

if(i>=k){

set.remove((long)nums[i-k]);

}

}

return false;

}

}

Runtime: **29 ms**

Memory Usage: **41.8 MB**

Please give me a clap if this article helped you. This is my first article on medium, so suggest for improvements.

Thanks and keep reading :)