Contains Duplicate III

Problem Statement

In this challenge, you are provided with an integer array nums and two integer values, indexDiff and valueDiff. Your task is to determine if there exists a pair of indices (i, j) in the array where the following conditions are all satisfied:

• The indices i and j are distinct (i.e., i is not equal to j).
• The absolute difference between i and j does not exceed indexDiff (abs(i - j) <= indexDiff).
• The absolute difference between the values at these indices does not exceed valueDiff (abs(nums[i] - nums[j]) <= valueDiff).

The function should return true if such a pair exists, otherwise false.

Examples

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.

Constraints

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

Approach and Intuition

The problem requires checking pairs in an array to fulfill both index and value difference constraints. Here's how to think about it:

1. Sliding Window Approach: Given the limitation by indexDiff on how far apart indices can be, this problem naturally leans towards a sliding window or two-pointer approach.

   • Iterate over the array and for each element, consider it as nums[i].
   • Create a window (or subarray) that starts from i+1 to min(i + indexDiff, len(nums) - 1).
   • Check each element within this window:
     • If any satisfies abs(nums[i] - nums[j]) <= valueDiff, return true.

2. Use of Appropriate Data Structure: To efficiently check the condition abs(nums[i] - nums[j]) <= valueDiff, a balanced tree or a sorted data structure might help, but given typical constraint sizes, a simpler approach might work adequately, using direct computation.

3. Boundary Checks:

   • If valueDiff is 0, we are looking for exact duplicates within the allowed index range.
   • Always ensure that for the sliding window end point does not exceed array boundaries.

With respect to the provided examples:

• Example 1: "nums = [1,2,3,1], indexDiff = 3, valueDiff = 0". Directly iterate through nums and for each i, check other indices within the valid range. Here, nums[0] and nums[3] both are 1 and within index distance 3, hence, true.

• Example 2: Despite similar checks as in Example 1, no pairs (i, j) satisfy all given conditions due to larger differences in values compared to the allowed valueDiff, thus, false.

Solutions

class Solution {
public:
    long calculateBucketID(long element, long width) { 
        return element < 0 ? (element + 1) / width - 1 : element / width; 
    }
    
    bool hasNearbyDuplicate(vector<int>& elements, int range, int tolerance) {
        if (tolerance < 0) return false;
        unordered_map<long, long> mapBuckets;
        long width = (long)tolerance + 1;
        for (int i = 0; i < elements.size(); ++i) {
            long bucketID = calculateBucketID(elements[i], width);
            if (mapBuckets.count(bucketID)) return true;
            if (mapBuckets.count(bucketID - 1) &&
                abs(elements[i] - mapBuckets[bucketID - 1]) < width)
                return true;
            if (mapBuckets.count(bucketID + 1) &&
                abs(elements[i] - mapBuckets[bucketID + 1]) < width)
                return true;
            mapBuckets[bucketID] = (long)elements[i];
            if (i >= range) {
                mapBuckets.erase(calculateBucketID(elements[i - range], width));
            }
        }
        return false;
    }
};