Sunday, October 11, 2015

Leetcode: Contains Duplicate III

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.

Understand the problem:
The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk). 

We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which is a sliding window. So when we insert an element to the treeSet, we need to remove one from the end. 

So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.

Code (Java):
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1 || k <= 0 || t < 0) {
            return false;
        }
        
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            Integer floor = treeSet.floor(nums[i] + t);
            Integer ceil = treeSet.ceiling(nums[i] - t);
            
            if ((floor != null && floor >= nums[i]) 
                || (ceil != null && ceil <= nums[i])) {
                return true;
            }
            
            treeSet.add(nums[i]);
            
            if (i >= k) {
                treeSet.remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

2 comments:

  1. Very elegant answer!!!.

    It is failing for the input [-2147483648,-2147483647]
    3
    3

    ReplyDelete
    Replies
    1. -2147483648 is the MINIMUM_VALUE and 2147483647 is the MAX_VALUE that an 32-bit int variable can hold. Summation and substraction operations on those values lead to roll overs. (e.g. 2147483647+1 will be rolled over to -2147483648). For this code, operations +t and -t causes the same problem. So TreeSet should consist of variables, thus floor and ceiling values should be Long instead of Integer.

      Delete