Our blog, keeping you up-to-date on our latest news.

 

[Leetcode]Contains Duplicate III

June 28, 2015 at 10:36 pm | Algorithms | No comment

 

Overview

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.

Thoughts

the thought process is to exam the numbers within k distances, and see if there is aa number having a difference smaller than t. The most intuitive solution is to have two loops, the first loop to go through all numbers in the array, and the inside loop check every number within k difference, to see if it is a almost duplicate number.

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums==null || nums.length<=1 || k<=0 || t<0)
            return false;
        for(int i = 1; i<nums.length; i++){
            for(int j = Math.max(0, i-k); j<i; j++){
                if(Math.abs(nums[i]-nums[j])<=t)
                    return true;
            }
        }
        return false;
    }
}

but obviously, this solution is not quite good from time efficiency perspecitive. The time complexity is O(n*k), the worst case is O(n^2). So to optimize this, we should ask one question: do we really need to exam all items within k distances?

the answer is of course not, we can maintain an binary search tree, to identify the numbers with smallest difference. and the search of the time complexity will be reduced from O(n) to O(lg).

Solution

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> window = new TreeSet<Integer>();
 
        for(int i = 0; i<nums.length; i++){
 
            Integer floor = window.floor(nums[i]);
            Integer ceiling = window.ceiling(nums[i]);
            if(floor != null && new Long(nums[i])- new Long(floor)<= new Long(t))
                return true;
            if(ceiling != null && new Long(ceiling)- new Long(nums[i])<= new Long(t))
                return true;
            if(window.size()==k)
                window.remove(nums[i-k]);
            window.add(nums[i]);
        }
        return false;
    }
}

Notes

1. I choose the treeset, which is using treemap to hold all the elements. And the treemap is an implemenation of black-red tree.
2. we have to be very careful about the edge condwitions. especially when the Integer number is extremely large, and the difference might be exceed the maxium value of an Integer.

<< Back to Blog Discuss this post

 
Comments are closed.