Leetcode Contains Duplicate III problem solution

YASH PAL,

In this Leetcode Contains Duplicate III problem solution we have given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] – nums[j]) <= t and abs(i – j) <= k.

Leetcode Contains Duplicate III problem solution

Problem solution in Python.

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t == 0 and len(nums) == len(set(nums)):
            return False
        
        for i in range(len(nums)-1):
            for j in range(i+1, min(i+1+k, len(nums))):
                if abs(nums[i] - nums[j]) <= t:
                    return True
        
        return False

Problem solution in Java.

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeMap<Long,Integer> treemap=new TreeMap<>();        
        for(int i=0;i<nums.length;i++){
            if(treemap.size() > k) 
                treemap.remove((long)nums[i - k - 1]);
            Long ceil = treemap.ceilingKey((long)nums[i]);
            Long floor = treemap.floorKey((long)nums[i]);
            if(ceil != null && ceil <= (long)nums[i] + t)
                return true;
            if(floor != null && floor >= (long)nums[i] - t)
                return true;
            treemap.put((long)nums[i],i);
        }
        return false;
    }
}

Problem solution in C++.

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> s;
        for(int i=0;i<nums.size();i++){
            if(i>k)
                s.erase(nums[i-k-1]);
            auto pos=s.lower_bound(long(nums[i])-long(t));
            if(pos!=s.end() && *pos-nums[i]<=t)
                return true;
            s.insert(nums[i]);
        }
        return false;
    }
};

coding problems solutions