Find duplicates (within k indicies)

Tag: Palantir

• http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
• http://www.shuatiblog.com/blog/2015/04/12/duplicate-within-k-distance/
• http://www.geeksforgeeks.org/check-given-array-contains-duplicate-elements-within-k-distance/

Problem: Given an array of values, design and code an algorithm that returns whether there are two duplicates within k indices of each other?

Solution:

Using a set to maintain a window of size K storing the elements appeared in k distance.

public boolean dupWithinK(int k, int[] arr) {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < arr.length; i++) {
        // If already present n hash, then we found 
        // a duplicate within k distance
        if (set.contains(arr[i])) {
            return true;
        }

        // Add this item to hashset
        set.add(arr[i]);
        // Remove the k+1 distant item
        if (i >= k)
            set.remove(arr[i - k]);
        }
    }
    return false;
}

Follow up: fuzzy

• https://github.com/DeanWen/leetCodeInterview/blob/master/Interview/Palantir/Find%20Duplicates%20in%20Unsorted%20Array.java

/*
*Given an unsorted list of integers, 
*return true if the list contains any fuzzy duplicates within k indices of each element. 
*A fuzzy duplicate is another integer within d of the original integer. 
*Example: 
*    [1, 5, 2, 9] k = 2  d = 1 (2 - 1 = a[0]-a[2] <= 2) -- true
*    [1, 5, 9, 2] k = 2  d = 1 (2 - 1 = a[0]-a[3] > 2) -- false
*/
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (nums == null || nums.length == 0 || k <= 0) {
        return false;
    }

    TreeSet<Integer> values = new TreeSet<>();
    for (int ind = 0; ind < nums.length; ind++) {

        Integer floor = values.floor(nums[ind] + t);//upper bond
        Integer ceil = values.ceiling(nums[ind] - t);//lower bond

        /* 
         * TreeSet.floor: Returns the greatest element
         * in this set less than or equal to the given element, 
         * or null if there is no such element.

         * Treeset.ceiling: Returns the least element 
         * in this set greater than or equal to the given element, 
         * or null if there is no such element.
         *
         */

        if ((floor != null && floor >= nums[ind])
                || (ceil != null && ceil <= nums[ind])) {
            return true;
        }

        values.add(nums[ind]);
        if (ind >= k) {
            values.remove(nums[ind - k]);
        }
    }

    return false;
}