Table of Contents

# Contains Duplicate III – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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`

.

**Example 1:**

Input:nums = [1,2,3,1], k = 3, t = 0Output:true

**Example 2:**

Input:nums = [1,0,1,1], k = 1, t = 2Output:true

**Example 3:**

Input:nums = [1,5,9,1,5,9], k = 2, t = 3Output:false

**Constraints:**

`1 <= nums.length <= 2 * 10`

^{4}`-2`

^{31}<= nums[i] <= 2^{31}- 1`0 <= k <= 10`

^{4}`0 <= t <= 2`

^{31}- 1

# C++ Contains Duplicate III LeetCode Solution

```
``````
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n = nums.size();
if(n == 0 || k < 0 || t < 0) return false;
unordered_map<int,int> buckets;
for(int i=0; i<n; ++i) {
int bucket = nums[i] / ((long)t + 1);
// For negative numbers, we need to decrement bucket by 1
// to ensure floor division.
// For example, -1/2 = 0 but -1 should be put in Bucket[-1].
// Therefore, decrement by 1.
if(nums[i] < 0) --bucket;
if(buckets.find(bucket) != buckets.end()) return true;
else {
buckets[bucket] = nums[i];
if(buckets.find(bucket-1) != buckets.end() && (long) nums[i] - buckets[bucket-1] <= t) return true;
if(buckets.find(bucket+1) != buckets.end() && (long) buckets[bucket+1] - nums[i] <= t) return true;
if(buckets.size() > k) {
int key_to_remove = nums[i-k] / ((long)t + 1);
if(nums[i-k] < 0) --key_to_remove;
buckets.erase(key_to_remove);
}
}
}
return false;
}
};
```

# Java Contains Duplicate III LeetCode Solution

```
``````
private long getID(long i, long w) {
return i < 0 ? (i + 1) / w - 1 : i / w;
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> d = new HashMap<>();
long w = (long)t + 1;
for (int i = 0; i < nums.length; ++i) {
long m = getID(nums[i], w);
if (d.containsKey(m))
return true;
if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
return true;
if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
return true;
d.put(m, (long)nums[i]);
if (i >= k) d.remove(getID(nums[i - k], w));
}
return false;
}
```

# Python 3 Contains Duplicate III LeetCode Solution

```
``````
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0: return False
n = len(nums)
d = {}
w = t + 1
for i in xrange(n):
m = nums[i] / w
if m in d:
return True
if m - 1 in d and abs(nums[i] - d[m - 1]) < w:
return True
if m + 1 in d and abs(nums[i] - d[m + 1]) < w:
return True
d[m] = nums[i]
if i >= k: del d[nums[i - k] / w]
return False
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below