Contains Duplicate III

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;
    }
};

The provided C++ solution addresses the problem of determining whether an array contains duplicates within a certain index range and value difference. Edit the hasNearbyDuplicate function to explore an array of integers, using a system of logical bucketing whereby each element is assigned to a computed bucket ID based on its value and the allowed tolerance.

• Calculate Bucket ID: Private member function calculateBucketID computes and returns the bucket ID for a given element based on its value and the specified width (tolerance + 1). It accounts for negative elements correctly by adjusting the bucket computation, ensuring accurate mapping.
• Examine Duplicates with Conditions:
  1. Initialize a hash map mapBuckets to store elements mapped to their respective bucket IDs.
  2. Define width as the tolerance increased by one, used for bucketing.
  3. Iterate through the vector of elements.
  4. For each element, determine the current element's bucket ID.
  5. Check if this bucket ID, or the neighboring bucket IDs (one above or below), already exist in mapBuckets and meet the criteria of having an absolute difference less than width. If found, return true, indicating a duplicate under the specified conditions.
  6. Update the current bucket ID in mapBuckets with the element.
  7. If the current index surpasses the specified range (range), remove the oldest element's bucket from mapBuckets to maintain the constraint of considering only the nearby elements.
• Conclusion: If no such duplicate is found by the end of the array, return false. This solution effectively uses a sliding window approach combined with bucketing to efficiently find duplicates within the specified range and tolerance in terms of indices and values.

class Solution {
    // Determine the bucket ID
    private long bucketId(long x, long width) {
        return Math.floorDiv(x, width);
    }
    
    public boolean checkDuplicatesWithinK(int[] nums, int k, int t) {
        if (t < 0) return false;
        Map<Long, Long> map = new HashMap<>();
        long bucketWidth = (long) t + 1;
        for (int i = 0; i < nums.length; ++i) {
            long currentBucketId = bucketId(nums[i], bucketWidth);
            if (map.containsKey(currentBucketId)) return true;
            if (map.containsKey(currentBucketId - 1) && Math.abs(nums[i] - map.get(currentBucketId - 1)) < bucketWidth)
                return true;
            if (map.containsKey(currentBucketId + 1) && Math.abs(nums[i] - map.get(currentBucketId + 1)) < bucketWidth)
                return true;
            map.put(currentBucketId, (long) nums[i]);
            if (i >= k) map.remove(bucketId(nums[i - k], bucketWidth));
        }
        return false;
    }
}

In the Java solution to the "Contains Duplicate III" problem, the task is to determine if there are any duplicates in the array such that:

• The absolute difference between two elements is at most t.
• The absolute difference between their indices is at most k.

Here's how the solution works:

• Define a method bucketId(long x, long width) to calculate the bucket ID for an element considering the bucket width, which is set to t + 1. The bucket ID is computed using Math.floorDiv(x, width).
• In the method checkDuplicatesWithinK, it initially checks if t < 0, immediately returning false if true, as a negative t doesn't make sense in the context of absolute differences.
• The program then initializes a HashMap to track the elements and their corresponding bucket IDs.
• Iterate through the array nums. For each element:
  • Calculate its bucket ID.
  • Check if this bucket or its neighboring buckets (current ID +1 and current ID -1) already contain a value close enough (within the bucket width) to the current element.
• If such a value is found, return true as a duplicate exists within the specified distance and difference constraints.
• Store each element in its appropriate bucket in the map.
• If the window of inspection (determined by k) slides beyond the index i, remove the element that falls out of this range from the map using its bucket ID to maintain only relevant comparisons.
• After checking all elements, return false if no such pair is found.

This implementation cleverly uses bucket sorting to reduce the complexity of checking each pair of indices in the naive approach. This ensures that each element is compared only with its immediate neighbors in a controlled bucket environment, optimizing the search for qualifying duplicate values. Adjusting the bucket storage dynamically as the index moves beyond k keeps the memory usage efficient and operations swift.

class Solution:
    
    def calculate_bucket_id(self, value, width):
        return value // width
    
    def check_nearby_dupe(self, elements, range_limit, difference):
        if difference < 0:
            return False
        hash_map = {}
        bucket_width = difference + 1
        for index in range(len(elements)):
            current_bucket = self.calculate_bucket_id(elements[index], bucket_width)
            if current_bucket in hash_map:
                return True
            if (current_bucket - 1 in hash_map and abs(elements[index] - hash_map[current_bucket - 1]) < bucket_width):
                return True
            if (current_bucket + 1 in hash_map and abs(elements[index] - hash_map[current_bucket + 1]) < bucket_width):
                return True
            hash_map[current_bucket] = elements[index]
            if index >= range_limit:
                del hash_map[self.calculate_bucket_id(elements[index - range_limit], bucket_width)]
        return False

The Python solution involves checking whether any two indices in an array differ by at most a given value difference, and the values at those indices differing by at most range_limit. This problem is approached using a bucketing method.

1. Define a function calculate_bucket_id to compute the bucket number for each element in the array, based on the element's value and the bucket width.
2. In check_nearby_dupe, define a bucket width as difference + 1.
3. Create a dictionary to store the last value encountered in each bucket.
4. Iterate through all elements in the array:
   • Calculate the bucket for the current element.
   • Check if the current bucket already exists in the dictionary. If yes, duplicate values are within the acceptable proximity, and return True.
   • Check the previous and the next buckets for proximity conditions, returning True if any condition matches.
   • Update the dictionary to store the current value in the current bucket.
   • If the number of processed elements exceeds range_limit, remove the oldest element from the dictionary to maintain the range boundary.
5. If no conditions are met throughout the loop, return False.

This method uses a sliding window technique mapping elements to buckets to ensure efficient look-ups and maintain the conditions given by the problem constraints.