LeetCode 220: Contains Duplicate III Solution
Master LeetCode problem 220 (Contains Duplicate III), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
220. Contains Duplicate III
Problem Explanation
Explanation
To solve this problem, we can iterate through each element in the array and maintain a sliding window of size indexDiff. For each element, we check if there exists any previous element within the window such that the absolute difference between the current element and the previous element is less than or equal to valueDiff.
We can use a TreeSet (Red-Black Tree) in Java or a multiset in C++ to efficiently retrieve the previous element within the window. By maintaining this window, we can efficiently check if the conditions are satisfied.
- Time complexity: O(n * log(min(n, k))), where n is the length of the input array and k is the size of the window.
- Space complexity: O(min(n, k))
Solution Code
import java.util.TreeSet;
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Long floor = set.floor((long) nums[i] + valueDiff);
Long ceiling = set.ceiling((long) nums[i] - valueDiff);
if ((floor != null && floor >= nums[i]) || (ceiling != null && ceiling <= nums[i])) {
return true;
}
set.add((long) nums[i]);
if (i >= indexDiff) {
set.remove((long) nums[i - indexDiff]);
}
}
return false;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 220 (Contains Duplicate III)?
This page provides optimized solutions for LeetCode problem 220 (Contains Duplicate III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 220 (Contains Duplicate III)?
The time complexity for LeetCode 220 (Contains Duplicate III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 220 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 220 in Java, C++, or Python.