[LeetCode] Contains Duplicate III

Contains Duplicate |||

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 = 3

For the scenarios involving minimum(-2147483648) or maximum(2147483647) Integer values as elements in the array, using a TreeSet with generic type ‘Integer’ can cause Overflow 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 :)