Last updated on October 10th, 2024 at 12:48 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*

*List of all LeetCode Solution*

## Topics

Ordered-Map, Sort

## Companies

Airbnb, Palantir

## Level of Question

Hard

**Contains Duplicate III LeetCode Solution**

## Table of Contents

**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 = 0Output: trueExplanation: 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) <= 0Example 2:Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3Output: falseExplanation: 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

**Sliding Window with Multiset**: The code uses a**multiset**named**pre**to keep a window of the last k elements.**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**.**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(logk).

#### 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

**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.**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.**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

**Brute Force Approach**: The code uses two nested loops to check each pair of indices (i,j) where ∣i−j∣≤k.**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

**Bucketization**: Similar to the Java solution, it maps each number to a bucket.**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.**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.