Contains Duplicate Iii

                                            
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        set<long> window;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > indexDiff) {
                window.erase(nums[i - indexDiff - 1]);
            }
            auto it = window.lower_bound((long)nums[i] - valueDiff);
            if (it != window.end() && *it <= (long)nums[i] + valueDiff) {
                return true;
            }
            window.insert(nums[i]);
        }
        return false;
    }
};

                                            
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Integer> set = new TreeSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            Integer floor = set.floor(nums[i] + valueDiff);
            Integer ceiling = set.ceiling(nums[i] - valueDiff);
            
            if ((floor != null && floor >= nums[i]) || (ceiling != null && ceiling <= nums[i])) {
                return true;
            }
            
            set.add(nums[i]);
            
            if (i >= indexDiff) {
                set.remove(nums[i - indexDiff]);
            }
        }
        
        return false;
    }
}

                                            
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, indexDiff, valueDiff):
        if indexDiff <= 0:
            return False
        
        seen = {}
        
        for i in range(len(nums)):
            if i > indexDiff:
                del seen[nums[i - indexDiff - 1] // (valueDiff + 1)]
            
            bucket = nums[i] // (valueDiff + 1)
            
            for key in [bucket, bucket - 1, bucket + 1]:
                if key in seen and abs(nums[i] - seen[key]) <= valueDiff:
                    return True
            
            seen[bucket] = nums[i]
        
        return False

                                            
bool containsNearbyAlmostDuplicate(int* nums, int 
numsSize, int indexDiff, int valueDiff) {
    if (nums == NULL || numsSize <= 1) {
        return false;
    }
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (abs(i - j) <= indexDiff && abs(nums[i] - nums[j]) <= valueDiff) {
                return true;
            }
        }
    }
    
    return false;
}

                                            
public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        SortedSet<long> set = new SortedSet<long>();
        for (int i = 0; i < nums.Length; i++) {
            if (i > indexDiff) {
                set.Remove(nums[i - indexDiff - 1]);
            }
            var index = set.GetViewBetween((long)nums[i] - valueDiff, (long)nums[i] + valueDiff).GetEnumerator();
            if (index.MoveNext()) {
                return true;
            }
            set.Add(nums[i]);
        }
        return false;
    }
}

                                            
/**
 * @param {number[]} nums
 * @param {number} indexDiff
 * @param {number} valueDiff
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
    const set = new Set();
    for (let i = 0; i < nums.length; i++) {
        for (let j = Math.max(0, i - indexDiff); j < i; j++) {
            if (Math.abs(nums[i] - nums[j]) <= valueDiff) {
                return true;
            }
        }
        for (let j = i + 1; j <= Math.min(i + indexDiff, nums.length - 1); j++) {
            if (Math.abs(nums[i] - nums[j]) <= valueDiff) {
                return true;
            }
        }
    }
    return false;
};

To solve this coding challenge, we need to design an algorithm that checks if there exists any pair of indices \( (i, j) \) meeting the given conditions. Let's break this task down step by step to understand the methodology and then provide the pseudocode with extensive comments.

Step-by-Step Explanation

Understanding the Objective :

We need to determine if there are two distinct indices \( i \) and \( j \) in the array
nums

such that:

\( i \neq j \)
\( |i - j| \leq \text{indexDiff} \)
\( |\text{nums}[i] - \text{nums}[j]| \leq \text{valueDiff} \)

Constraints :

Array length constraints \( 2 \leq \text{nums.length} \leq 10^5 \)
Value constraints \( -10^9 \leq \text{nums}[i] \leq 10^9 \)
\( 1 \leq \text{indexDiff} \leq \text{nums.length} \)
\( 0 \leq \text{valueDiff} \leq 10^9 \)

Initial Thoughts :

Using a brute-force approach, comparing every possible pair may not be efficient due to the size constraints.
Instead, we need a more efficient algorithm using a sliding window and a hash-based approach for quick lookups.

Sliding Window Approach with Bucketing :

We'll use a hash map to keep track of elements within the current sliding window of
indexDiff

.
Each element
nums[i]

is mapped to a "bucket" based on its value divided by
(valueDiff + 1)

. This helps manage the range efficiently.

Pseudocode :

                                            
function containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):
if indexDiff <= 0:
return False

# Dictionary to maintain the sliding window
seen_buckets = {}

# Iterate through each number in the array
for i from 0 to length(nums) - 1:
# Clean the bucket window when it exceeds the indexDiff
if i > indexDiff:
old_bucket = nums[i - indexDiff - 1] // (valueDiff + 1)
delete seen_buckets[old_bucket]

# Find the current bucket of the element
current_bucket = nums[i] // (valueDiff + 1)

# Check the current bucket and its neighboring buckets for possible matches
for bucket in [current_bucket, current_bucket - 1, current_bucket + 1]:
if bucket in seen_buckets and abs(nums[i] - seen_buckets[bucket]) <= valueDiff:
return True

# Insert the current element's value in the bucket map
seen_buckets[current_bucket] = nums[i]

return False

Detailed Steps in Pseudocode

Function Initialization :

The function
containsNearbyAlmostDuplicate

takes three parameters:
nums

,
indexDiff

, and
valueDiff

.
If
indexDiff

is less than or equal to zero, it returns False immediately because the index difference constraint cannot be satisfied.

Hash Map Initialization :

We initialize an empty dictionary
seen_buckets

to store elements within the current sliding window. This will help in quickly checking if the conditions are met.

Iterate Through the Array :

Start a loop from 0 to the length of
nums

minus one.
For each index
i

, check if the index exceeds the allowed index difference (
indexDiff

). If it does, remove the element outside the current sliding window from
seen_buckets

.

Determine Buckets :

Compute the current bucket for
nums[i]

by dividing it by
(valueDiff + 1)

.

Check Neighboring Buckets :

For each bucket that includes the current bucket, and its immediate neighbors (previous and next bucket), check if there exists a match in
seen_buckets

.
If a matching element is found that satisfies the value difference condition, return True.

Update the Hash Map :

If no matching element is found, update the
seen_buckets

with the current element's value.

Return Result :

If no pair is found after processing the entire array, return False.

This approach ensures we have an efficient solution with a time complexity approximately of \( O(n) \) due to the single pass and constant-time lookups and deletions within the sliding window. This is crucial for handling large inputs within the given constraints effectively.