220. Contains Duplicate III LeetCode Solution

In this guide, you will get 220. Contains Duplicate III LeetCode Solution with the best time and space complexity. The solution to Contains Duplicate III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Contains Duplicate III solution in C++
4. Contains Duplicate III solution in Java
5. Contains Duplicate III solution in Python
6. Additional Resources

Problem Statement of Contains Duplicate III

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) abs(0 – 3) <= 3
abs(nums[i] – nums[j]) 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.

Constraints:

2 <= nums.length <= 105
-109 <= nums[i] <= 109
1 <= indexDiff <= nums.length
0 <= valueDiff <= 109

Complexity Analysis

• Time Complexity: O(n\log k)
• Space Complexity: O(k)

220. Contains Duplicate III LeetCode Solution in C++

class Solution {
 public:
  bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff,
                                     int valueDiff) {
    set<long> window;

    for (int i = 0; i < nums.size(); ++i) {
      if (const auto it =
              window.lower_bound(static_cast<long>(nums[i]) - valueDiff);
          it != window.cend() && *it - nums[i] <= valueDiff)
        return true;
      window.insert(nums[i]);
      if (i >= indexDiff)
        window.erase(nums[i - indexDiff]);
    }

    return false;
  }
};
/* code provided by PROGIEZ */

220. Contains Duplicate III LeetCode Solution in Java

class Solution {
  public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    TreeSet<Long> set = new TreeSet<>();

    for (int i = 0; i < nums.length; ++i) {
      final long num = (long) nums[i];
      final Long ceiling = set.ceiling(num); // The smallest num >= nums[i]
      if (ceiling != null && ceiling - num <= valueDiff)
        return true;
      final Long floor = set.floor(num); // The largest num <= nums[i]
      if (floor != null && num - floor <= valueDiff)
        return true;
      set.add(num);
      if (i >= indexDiff)
        set.remove((long) nums[i - indexDiff]);
    }

    return false;
  }
}
// code provided by PROGIEZ

220. Contains Duplicate III LeetCode Solution in Python

class Solution {
 public:
  bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff,
                                     int valueDiff) {
    if (nums.empty() || indexDiff <= 0 || valueDiff < 0)
      return false;

    const long mn = ranges::min(nums);
    const long diff = valueDiff + 1L;  // In case that `valueDiff` equals 0.
    // Use long because the corner case INT_MAX - (-1) will overflow.
    unordered_map<long, long> bucket;

    for (int i = 0; i < nums.size(); ++i) {
      const long num = nums[i];
      const long key = getKey(num, mn, diff);
      if (bucket.contains(key))  // the current bucket
        return true;
      if (bucket.contains(key - 1) &&
          num - bucket[key - 1] < diff)  // the left adjacent bucket
        return true;
      if (bucket.contains(key + 1) &&
          bucket[key + 1] - num < diff)  // the right adjacent bucket
        return true;
      bucket[key] = num;
      if (i >= indexDiff)
        bucket.erase(getKey(nums[i - indexDiff], mn, diff));
    }

    return false;
  }

 private:
  int getKey(long num, long mn, long diff) {
    return (num - mn) / diff;
  }
};
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.