contains duplicate III

fishercoder1534 · fishercoder1534 · commit b28adf5d161d · 2016-08-06T18:09:33.000-07:00
diff --git a/MEDIUM/src/medium/ContainsDuplicateIII.java b/MEDIUM/src/medium/ContainsDuplicateIII.java
@@ -0,0 +1,105 @@
+package medium;
+
+import java.util.TreeSet;
+
+/**
+ * 220. Contains Duplicate III QuestionEditorial Solution My Submissions Total Accepted: 33823 Total
+ * Submissions: 176491 Difficulty: Medium Given an array of integers, find out whether there are two
+ * distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at
+ * most t and the difference between i and j is at most k.
+ */
+public class ContainsDuplicateIII {
+    /**
+     * TreeSet: per Java doc, is a NavigableSet implementation based on a TreeMap. The elements are ordered
+     * using their natural ordering, or by a Comparator provided at set creation time, depending on
+     * which constructor is used. This implementation provides guaranteed log(n) time cost for the
+     * basic operations (add, remove and contains).
+     */
+    
+    /**
+     * TreeSet turns out to be a super handy data structure for this problem. It implements Set
+     * interface and keeps elements in sorted order, plus it has two very handy APIs:
+     * 
+     * https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#ceiling(E): Returns the
+     * least element in this set greater than or equal to the given element, or null if there is no
+     * such element.
+     * 
+     * https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#floor(E): Returns the
+     * greatest element in this set less than or equal to the given element, or null if there is no
+     * such element.
+     * 
+     * Idea: loop through this array, keep adding each element into the TreeSet, also keep an eye on
+     * the size of the TreeSet, if it's greater than the required distance of k, then we remove the
+     * left-most or oldest one from the set. For each element, we get the current floor and the
+     * current ceiling and see if it works, if it does, then we return true immediately, otherwise,
+     * we continue. Return false when we finished the loop.
+     */
+
+    //Really, computing is all about data structures! Cool! Learned the gist again!
+    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
+        TreeSet<Integer> set = new TreeSet<Integer>();
+        for(int i = 0; i < nums.length; i++){
+            Integer s = set.ceiling(nums[i]);//take the smallest greater number than nums[i] is there exists
+            if(s != null && s - nums[i] <= t) return true;//it must be s - nums[i] here, otherwise, cases like [4,2] 2, 1 wont' pass, because we'll get 2-4 = -2 which is a negative number that for sure will be smaller than t
+            Integer g = set.floor(nums[i]);//take the biggest smaller number than nums[i] if there exists
+            if(g != null && (long) nums[i] - g <= t) return true;
+            set.add(nums[i]);
+            if(set.size() > k) set.remove(nums[i-k]);//set doesn't have indices and it's not ordered, we could only specify the element 
+            //that we want to remove, this element is nums[i-k]
+        }
+        return false;
+    }
+
+    //My naive approach prior to looking on Discuss: 
+    //it must be a O(n^2), I cannot think of any algorithms that do better than this
+    // as expected, this following algorithm made it to 29/31 test cases and failed by the last
+    // extreme test case due to TLE.
+    public boolean containsNearbyAlmostDuplicate_TLE(int[] nums, int k, int t) {
+        for (int i = 0; i < nums.length; i++) {
+            for (int j = i + 1; j < nums.length; j++) {
+                long res = nums[j] - nums[i];// use long type to avoid overflow
+                if (Math.abs(res) <= t && j - i <= k)
+                    return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * converting to (long) is essential, otherwise cases like this:
+     * 
+     * [-1,2147483647]
+     * 
+     * 1
+     * 
+     * 2147483647
+     * 
+     * will overflow, i.e. Integer in Java is 32 bit which means Integer.MAX_VALUE =2147483647 and
+     * Integer.MIN_VALUE = -2147483648, thus 2147483647 -(-1) = 2147483647+1 =-2147483648 instead of
+     * 2147483648 (Java Integer won’t have this number), causing this test case to fail.
+     */
+
+    public static void main(String... strings) {
+        ContainsDuplicateIII test = new ContainsDuplicateIII();
+        // int[] nums = new int[]{-1, -1};
+        // int k = 1;
+        // int t = 0;
+
+//        int[] nums = new int[] { 1, 2 };
+//        int k = 0;
+//        int t = 1;
+        
+        int[] nums = new int[] { 4, 2 };
+        int k = 2;
+        int t = 1;
+
+        // int[] nums = new int[]{2, 2};
+        // int k = 3;
+        // int t = 0;
+
+        // int[] nums = new int[]{1};
+        // int k = 1;
+        // int t = 1;
+        System.out.println(test.containsNearbyAlmostDuplicate(nums, k, t));
+    }
+}
