Last updated on March 9th, 2025 at 10:15 pm

Here, we see a Contains Duplicate III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Ordered-Map, Sort

Companies

Airbnb, Palantir

Level of Question

Hard

Contains Duplicate III LeetCode Solution

1. Problem Statement

You are given an integer array nums and two integers indexDiff and valueDiff. Find a pair of indices (i, j) such that:

i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

Example 1:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:
Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Sliding Window with Buckets or Sets”. This pattern is used to maintain a window of size k and check for conditions within the window. The window is dynamically updated as the loop progresses, and the data structure (e.g., multiset, HashMap, or buckets) is used to efficiently check for the required conditions.

3. Code Implementation in Different Languages

3.1 Contains Duplicate III C++

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

3.2 Contains Duplicate III Java

 public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) return false;
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
            long bucket = remappedNum / ((long) t + 1);
            if (map.containsKey(bucket)
                    || (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t)
                        || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
                            return true;
            if (map.entrySet().size() >= k) {
                long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
                map.remove(lastBucket);
            }
            map.put(bucket, remappedNum);
        }
        return false;
    }
}

3.3 Contains Duplicate III JavaScript

var containsNearbyAlmostDuplicate = function(nums, k, t) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= i + k; j++) { // satisfies (1)
            if (j >= nums.length) break;
            let diff = Math.abs(nums[i] - nums[j]);
            if (diff <= t) { // satisfies (2)
                return true;
            }
        }
    }
    return false;
};

3.4 Contains Duplicate III Python

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0: return False # edge case 
        
        seen = {}
        for i, x in enumerate(nums): 
            bkt = x//(t+1)
            if bkt in seen and i - seen[bkt][0] <= k: return True 
            if bkt-1 in seen and i - seen[bkt-1][0] <= k and abs(x - seen[bkt-1][1]) <= t: return True 
            if bkt+1 in seen and i - seen[bkt+1][0] <= k and abs(x - seen[bkt+1][1]) <= t: return True 
            seen[bkt] = (i, x) 
        return False 

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * log(k))	O(k)
Java	O(n)	O(k)
JavaScript	O(n * k)	O(1)
Python	O(n)	O(k)

• C++ and Java use efficient data structures (multiset and HashMap) to maintain the sliding window, resulting in better performance.
• JavaScript uses a brute-force approach, which is less efficient for large inputs.
• Python uses a dictionary-based bucket approach, similar to Java, and achieves efficient performance.