Contains Duplicate III LeetCode Solution

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

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

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;
};
```Code language: C++ (cpp)```

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;
}
}
```Code language: Java (java)```

Contains Duplicate III Leetcode Solution JavaScript

``````/*
k = max size of window
t = max diff between nums[startOfWindow] and nums[endOfWindow]

We need to find if there are i and j such that (1) their size of window is <= k and (2) their diff is <= t.
*/
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)
let diff = Math.abs(nums[i] - nums[j]);
if (diff <= t) { // satisfies (2)
return true;
}
}
}
return false;
};
```Code language: JavaScript (javascript)```

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
```Code language: Python (python)```
Scroll to Top