Last updated on January 20th, 2025 at 11:10 pm
Here, we see a Contains Duplicate III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Ordered-Map, Sort
Companies
Airbnb, Palantir
Level of Question
Hard

Contains Duplicate III LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Sliding Window with Buckets or Sets”. This pattern is used to maintain a window of size k
and check for conditions within the window. The window is dynamically updated as the loop progresses, and the data structure (e.g., multiset
, HashMap
, or buckets
) is used to efficiently check for the required conditions.
3. Code Implementation in Different Languages
3.1 Contains Duplicate III 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; };
3.2 Contains Duplicate III 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; } }
3.3 Contains Duplicate III 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.4 Contains Duplicate III 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. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n * log(k)) | O(k) |
Java | O(n) | O(k) |
JavaScript | O(n * k) | O(1) |
Python | O(n) | O(k) |
- C++ and Java use efficient data structures (
multiset
andHashMap
) to maintain the sliding window, resulting in better performance. - JavaScript uses a brute-force approach, which is less efficient for large inputs.
- Python uses a dictionary-based bucket approach, similar to Java, and achieves efficient performance.