LeetCode //C - 220. Contains Duplicate III

220. 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) <= 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<=10^5$
• $-10^9<=nums[i]<=10^9$
• 1 <= indexDiff <= nums.length
• $0<=valueDiff<=10^9$

From: LeetCode
Link: 220. Contains Duplicate III

Solution:

Ideas:

1. Handling Negative Values:
   For negative values, adjust the bucket index to ensure proper bucket placement.

2. Checking Adjacent Buckets:
   Check the current bucket and adjacent buckets to ensure the difference constraints are met.

3. Sliding Window Maintenance:
   Remove elements that fall out of the indexDiff range to maintain the sliding window.

Code:

typedef struct Node {
    long key;
    int index;
    struct Node* next;
} Node;

typedef struct {
    Node** buckets;
    int size;
} HashMap;

HashMap* createHashMap(int size) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->buckets = (Node**)calloc(size, sizeof(Node*));
    map->size = size;
    return map;
}

int hash(long key, int size) {
    return (int)((key % size + size) % size);
}

void put(HashMap* map, long key, int index) {
    int bucketIndex = hash(key, map->size);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->index = index;
    newNode->next = map->buckets[bucketIndex];
    map->buckets[bucketIndex] = newNode;
}

bool get(HashMap* map, long key, int* index) {
    int bucketIndex = hash(key, map->size);
    Node* node = map->buckets[bucketIndex];
    while (node != NULL) {
        if (node->key == key) {
            *index = node->index;
            return true;
        }
        node = node->next;
    }
    return false;
}

void removeKey(HashMap* map, long key) {
    int bucketIndex = hash(key, map->size);
    Node* node = map->buckets[bucketIndex];
    Node* prev = NULL;
    while (node != NULL) {
        if (node->key == key) {
            if (prev == NULL) {
                map->buckets[bucketIndex] = node->next;
            } else {
                prev->next = node->next;
            }
            free(node);
            return;
        }
        prev = node;
        node = node->next;
    }
}

void freeHashMap(HashMap* map) {
    for (int i = 0; i < map->size; i++) {
        Node* node = map->buckets[i];
        while (node != NULL) {
            Node* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(map->buckets);
    free(map);
}

bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int indexDiff, int valueDiff) {
    if (numsSize < 2 || indexDiff < 1 || valueDiff < 0) {
        return false;
    }

    HashMap* map = createHashMap(numsSize);
    long bucketSize = (long)valueDiff + 1;

    for (int i = 0; i < numsSize; i++) {
        long num = (long)nums[i];
        long bucket = num / bucketSize;
        if (num < 0) bucket--; // Ensure proper bucket for negative values

        int index;

        if (get(map, bucket, &index)) {
            freeHashMap(map);
            return true;
        }
        if (get(map, bucket - 1, &index) && labs(num - (long)nums[index]) <= valueDiff) {
            freeHashMap(map);
            return true;
        }
        if (get(map, bucket + 1, &index) && labs(num - (long)nums[index]) <= valueDiff) {
            freeHashMap(map);
            return true;
        }

        put(map, bucket, i);

        if (i >= indexDiff) {
            long removeNum = (long)nums[i - indexDiff];
            long removeBucket = removeNum / bucketSize;
            if (removeNum < 0) removeBucket--;
            removeKey(map, removeBucket);
        }
    }

    freeHashMap(map);
    return false;
}