package leetcode;

import java.util.TreeSet;

/**
 * https://leetcode.com/problems/contains-duplicate-iii/
 */
public class Problem220 {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j <= (i + k) && j < nums.length; j++) {
//                int diff = Math.abs(nums[j] - nums[i]);
//                if (diff <= t) {
//                    return true;
//                }
//            }
//        }
        if (nums.length <= k || k <= 0 || t < 0) {
            return false;
        }
        if (k <= 0 || t < 0 || nums.length <= 1) {
            return false;
        }
        TreeSet<Integer> set = new TreeSet<>();
        int size = k + 1;
        if (size > nums.length) {
            size = nums.length;
        }
        for (int i = 0; i < size; i++) {
            set.add(nums[i]);
        }
        if (set.size() != size) {
            return true;
        }
        System.out.println(set);
        int a = set.first();
        int b = 0;
        if (set.size() > 1) {
            b = set.higher(set.first());
        }
        int diff = Math.abs(a - b);
        if (diff <= t) {
            return true;
        }
        int j = 0;
        for (int i = k + 1; i < nums.length; i++) {
            set.remove(nums[j]);
            set.add(nums[i]);
            if (set.size() != size) {
                return true;
            }
            System.out.println(set);
            a = set.first();
            b = 0;
            if (set.size() > 1) {
                b = set.higher(set.first());
            }
            diff = Math.abs(a - b);
            if (diff <= t) {
                return true;
            }
            j++;
        }
        return false;
    }

    public static void main(String[] args) {
        Problem220 prob = new Problem220();
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{0}, 0, 0)); // false
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{1}, 1, 1)); // false
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{-1, -1}, 1, 0)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{2, 1}, 1, 1)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{4, 2}, 2, 1)); // false
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{6, 2, 4, 8, 1, 3, 2}, 3, 1)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{6, 2, 4, 8, 1, 3, 2}, 2, 1)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{6, 2, 4, 8, 1, 3, 2}, 2, 1)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{2, 6, 4, 2}, 3, 1)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{2, 6, 4, 2}, 2, 1)); // false
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{2, 2}, 3, 0)); // true
        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{3, 6, 0, 4}, 2, 2)); // true
    }
}

@@ -511,95 +511,8 @@
   %7D%0A
-        if (nums.length %3C= k %7C%7C k %3C= 0 %7C%7C t %3C 0) %7B%0A            return false;%0A        %7D%0A
     
@@ -1056,35 +1056,36 @@
       %7D%0A        
-int
+long
  diff = Math.abs
@@ -1077,35 +1077,49 @@
 diff = Math.abs(
-a -
+(long) a - (long)
  b);%0A        if 
@@ -1118,32 +1118,39 @@
      if (diff %3C=
+ (long)
  t) %7B%0A          
@@ -1595,19 +1595,33 @@
 ath.abs(
-a -
+(long) a - (long)
  b);%0A   
@@ -1636,24 +1636,31 @@
  if (diff %3C=
+ (long)
  t) %7B%0A      
@@ -1715,32 +1715,292 @@
  j++;%0A        %7D%0A
+        a = set.pollFirst();%0A        while (!set.isEmpty()) %7B%0A            b = set.pollFirst();%0A            diff = (long) Math.abs((long) a - (long) b);%0A            if (diff %3C= (long) t) %7B%0A                return true;%0A            %7D%0A            a = b;%0A        %7D%0A
         return f
@@ -3221,24 +3221,26 @@
 )); // true%0A
+//
         Syst
@@ -3328,16 +3328,230 @@
 // true%0A
+//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B2, 2%7D, 3, 0)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B-1, 2147483647%7D, 1, 2147483647)); // false%0A
     %7D%0A%7D%0A

Update problem 220