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 = 0 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false
Constraints:
1 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 10 <= k <= 1040 <= t <= 231 - 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
