Question

Formatted question description: https://leetcode.ca/all/220.html

 220. Contains Duplicate III

 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

 @tag-array

Algorithm

Use TreeSet to solve, used to record the mapping between numbers and index.

most important difference between HashSet and TreeSet is ordering:

HashSet doesn’t guaranteed any order, while TreeSet maintains objects in Sorted order defined by either Comparable or Comparator method

Two pointers i and j are needed here. At first, both i and j point to 0, and then i starts to traverse the array to the right.

• If the difference between i and j is greater than k, and there is nums[j] in the map, delete it from the TreeSet and j move 1 step to the right. This ensures that the difference between the index of all the numbers in TreeSet is not greater than k,
• Then we use TreeSet subSet() function to find numbers greater than or equal to nums[i]-t, and the absolute value of the difference between all numbers less than this threshold and nums[i] will be greater than t.
• Then check all the following numbers, and return true if the absolute value of the difference between the numbers is less than or equal to t. Finally traverse the entire array and return false

The treeSet is essentially a balanced binary search tree.

• We put k elements in the treeSet, which is a sliding window.
• So when we insert an element to the treeSet, we need to remove one from the end.

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.

Code

Java

• Java
• C++
• Python

• import java.util.SortedSet;
  import java.util.TreeSet;
  
  public class Contains_Duplicate_III {
  
      class Solution {
          public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  
              if (nums == null || nums.length < 2 || k < 0 || t < 0) {
                  return false;
              }
  
              TreeSet<Long> set = new TreeSet<>(); // long because int will possibly be overflow
              for (int i = 0; i < nums.length; i++) {
                  long current = (long) nums[i];
                  long leftBoundary = (long) current - t;
                  long rightBoundary = (long) current + t + 1; // right boundary is exclusive, so +1
  
                  SortedSet<Long> sub = set.subSet(leftBoundary, rightBoundary);
  
                  if (sub.size() > 0) {
                      return true;
                  }
  
                  set.add(current);
  
                  // to keep the index diff <=k
                  if (i >= k) { // or if(set.size()>=k+1)
                      set.remove((long) nums[i - k]);
                  }
              }
  
              return false;
          }
      }
  
  }
  

• // OJ: https://leetcode.com/problems/contains-duplicate-iii/
  // Time: O(NlogK)
  // Space: O(K)
  class Solution {
  public:
      bool containsNearbyAlmostDuplicate(vector<int>& A, int k, int t) {
          if (t < 0) return false;
          multiset<long> s;
          for (int i = 0; i < A.size(); ++i) {
              if (i > k) s.erase(s.find(A[i - k - 1]));
              if (s.lower_bound((long)A[i] - t) != s.upper_bound((long)A[i] + t)) return true;
              s.insert(A[i]);
          }
          return false;
      }
  };
  

• '''
  bisect: maintaining a list in sorted order without having to sort the list after each insertion.
  https://docs.python.org/3/library/bisect.html
  
  bisect.bisect_left()
  Locate the insertion point for x in a to maintain sorted order.
  
  bisect.bisect_right() or bisect.bisect()
  Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.
  
  '''
  
  import bisect
  
  class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
      """
      :type nums: List[int]
      :type k: int
      :type t: int
      :rtype: bool
      """
      if k == 0:
        return False
      bst = []
      if k < 0 or t < 0:
        return False
      for i, num in enumerate(nums):
        idx = bisect.bisect_left(bst, num)
        if idx < len(bst) and abs(bst[idx] - num) <= t:
          return True
        if idx > 0 and abs(bst[idx - 1] - num) <= t:
          return True
        if len(bst) >= k:
          del bst[bisect.bisect_left(bst, nums[i - k])]
        bisect.insort(bst, num)
      return False
  
  

All Problems

All Solutions