@@ -0,0 +1,2048 @@
+package com.interview.misc;%0A%0Aimport java.util.Map;%0Aimport java.util.TreeMap;%0A%0A/**%0A * Date 10/26/2016%0A * @author Tushar Roy%0A *%0A * Given an array of integers,%0A * find out whether there are two distinct indices i and j in the array such that the difference%0A * between nums%5Bi%5D and nums%5Bj%5D is at most t and the difference between i and j is at most k.%0A *%0A * Solution%0A * Keep a tree map of num and its count. For every new number check if any number exists in map between%0A * num - t and num + t. If yes than return true. If no then add this number to the tree map. Also if tree map%0A * becomes of size k then drop the num%5Bi - k%5D number from the tree map.%0A *%0A * Time complexity O(nlogk)%0A *%0A * https://leetcode.com/problems/contains-duplicate-iii/%0A */%0Apublic class ContainsNumberWithinKDistance %7B%0A%0A    public boolean containsNearbyAlmostDuplicate(int%5B%5D nums, int k, int t) %7B%0A        if (nums.length == 0 %7C%7C k == 0) %7B%0A            return false;%0A        %7D%0A        TreeMap%3CInteger, Integer%3E map = new TreeMap%3C%3E();%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            int lowerEntry = nums%5Bi%5D - t - 1;%0A            int higherEntry = nums%5Bi%5D + t + 1;%0A            Map.Entry%3CInteger, Integer%3E higher = map.lowerEntry(higherEntry);%0A            if (higher != null && higher.getKey() %3E= nums%5Bi%5D) %7B%0A                return true;%0A            %7D%0A            Map.Entry%3CInteger, Integer%3E lower = map.higherEntry(lowerEntry);%0A            if (lower != null && lower.getKey() %3C= nums%5Bi%5D) %7B%0A                return true;%0A            %7D%0A            if (map.size() == k) %7B%0A                map.compute(nums%5Bi - k%5D, (key, val) -%3E %7B%0A                    if (val == 1) %7B%0A                        return null;%0A                    %7D else %7B%0A                        return val - 1;%0A                    %7D%0A                %7D);%0A            %7D%0A            map.compute(nums%5Bi%5D, (key, val) -%3E %7B%0A                if (val == null) %7B%0A                    return 1;%0A                %7D else %7B%0A                    return val + 1;%0A                %7D%0A            %7D);%0A        %7D%0A        return false;%0A    %7D%0A%7D%0A

Contains duplicate 3