Last updated on July 15th, 2024 at 04:25 am

Here, We see Contains Duplicate III LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Ordered-Map, Sort

Companies

Airbnb, Palantir

Level of Question

Hard

Contains Duplicate III LeetCode Solution

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.

1. Contains Duplicate III Leetcode Solution 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;
};

1.1 Explanation

1. Sliding Window with Multiset: The code uses a multiset named pre to keep a window of the last k elements.
2. Insert and Remove Elements: For each element, it first removes the element that is k+1 positions back (to maintain the window size). Then, it inserts the current element into the multiset.
3. Check for Almost Duplicate: It checks two neighbors of the inserted element to see if the difference with the current element is less than or equal to t.

1.2 Time Complexity

• O(n\log k), where n is the number of elements in the array. Each insertion and deletion in the multiset takes O(log⁡k).

1.3 Space Complexity

• O(k), for storing the last k elements in the multiset.

2. Contains Duplicate III Leetcode Solution 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;
    }
}

2.1 Explanation

1. Bucketization: The code maps each number to a “bucket” where the size of each bucket is t+1. This helps in ensuring that any two numbers within the same or adjacent buckets differ by at most t.
2. Check Neighbors: For each number, it checks the current, previous, and next bucket to see if any number in these buckets is within the t difference.
3. Sliding Window with HashMap: It maintains a sliding window of the last k elements by removing the element that is k+1 positions back.

2.2 Time Complexity

• O(n), where n is the number of elements in the array. Each insertion and deletion in the HashMap takes constant time.

2.3 Space Complexity

• O(k), for storing the last k elements in the HashMap.

3. Contains Duplicate III Leetcode Solution 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.1 Explanation

1. Brute Force Approach: The code uses two nested loops to check each pair of indices (i,j) where ∣i−j∣≤k.
2. Check Difference: For each pair, it checks if the absolute difference between the numbers is less than or equal to t.

3.2 Time Complexity

• O(nk), where n is the number of elements in the array. The inner loop runs k times for each element.

3.3 Space Complexity

• O(1), as no additional space is used except for a few variables.

4. Contains Duplicate III Leetcode Solution 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.1 Explanation

1. Bucketization: Similar to the Java solution, it maps each number to a bucket.
2. Check Neighbors: For each number, it checks the current, previous, and next bucket to see if any number in these buckets is within the t difference.
3. Sliding Window with Dictionary: It maintains a sliding window of the last k elements by removing the element that is k+1 positions back.

4.2 Time Complexity

• O(n), where n is the number of elements in the array. Each insertion and deletion in the dictionary takes constant time.

4.3 Space Complexity

• O(k), for storing the last k elements in the dictionary.