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 (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());
        }
        long diff = Math.abs((long) a - (long) b);
        if (diff <= (long) 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((long) a - (long) b);
            if (diff <= (long) t) {
                return true;
            }
            j++;
        }
        a = set.pollFirst();
        while (!set.isEmpty()) {
            b = set.pollFirst();
            diff = (long) Math.abs((long) a - (long) b);
            if (diff <= (long) t) {
                return true;
            }
            a = b;
        }
        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
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{2, 2}, 3, 0)); // true
//        System.out.println(prob.containsNearbyAlmostDuplicate(new int[]{-1, 2147483647}, 1, 2147483647)); // false
    }
}

@@ -211,308 +211,8 @@
 ) %7B%0A
-//        for (int i = 0; i %3C nums.length; i++) %7B%0A//            for (int j = i + 1; j %3C= (i + k) && j %3C nums.length; j++) %7B%0A//                int diff = Math.abs(nums%5Bj%5D - nums%5Bi%5D);%0A//                if (diff %3C= t) %7B%0A//                    return true;%0A//                %7D%0A//            %7D%0A//        %7D%0A
     
@@ -598,41 +598,8 @@
   %7D%0A
-        System.out.println(set);%0A
     
@@ -1060,45 +1060,8 @@
   %7D%0A
-            System.out.println(set);%0A
     
@@ -1605,32 +1605,32 @@
  = b;%0A        %7D%0A
+
         return f
@@ -1644,1544 +1644,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem220 prob = new Problem220();%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B0%7D, 0, 0)); // false%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B1%7D, 1, 1)); // false%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B-1, -1%7D, 1, 0)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B2, 1%7D, 1, 1)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B4, 2%7D, 2, 1)); // false%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B6, 2, 4, 8, 1, 3, 2%7D, 3, 1)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B6, 2, 4, 8, 1, 3, 2%7D, 2, 1)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B6, 2, 4, 8, 1, 3, 2%7D, 2, 1)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B2, 6, 4, 2%7D, 3, 1)); // true%0A//        System.out.println(prob.containsNearbyAlmostDuplicate(new int%5B%5D%7B2, 6, 4, 2%7D, 2, 1)); // false%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%7B3, 6, 0, 4%7D, 2, 2)); // 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

Solve problem 220