Sponsored
Sponsored
This approach utilizes a hash map (dictionary) to maintain a mapping between array elements and their indices. As we iterate through the array, we check if the current element already exists in the hash map. If it does, we calculate the difference between the current index and the stored index and check if it is less than or equal to k. If this condition is met, we return true. Otherwise, we update the hash map with the current index for the element.
Time Complexity: O(n), where n is the number of elements in the array, since each insert/find operation is linear.
Space Complexity: O(min(n, k)), where n is the number of elements in the array, because we store at most k elements in the map at any time.
1#include <stdbool.h>
2#include <stdlib.h>
3#include <string.h>
4
5struct HashMap {
6 int* keys;
7 int* values;
8 int size;
9 int capacity;
10};
11
12struct HashMap* createHashMap(int capacity) {
13 struct HashMap* map = (struct HashMap*)malloc(sizeof(struct HashMap));
14 map->keys = (int*)malloc(sizeof(int) * capacity);
15 map->values = (int*)malloc(sizeof(int) * capacity);
16 map->size = 0;
17 map->capacity = capacity;
18 return map;
19}
20
21void destroyHashMap(struct HashMap* map) {
22 free(map->keys);
23 free(map->values);
24 free(map);
25}
26
27int hashFindIndex(struct HashMap* map, int key) {
28 for (int i = 0; i < map->size; i++) {
29 if (map->keys[i] == key) {
30 return i;
31 }
32 }
33 return -1;
34}
35
36void hashInsert(struct HashMap* map, int key, int value) {
37 if (map->size < map->capacity) {
38 map->keys[map->size] = key;
39 map->values[map->size] = value;
40 map->size++;
41 }
42}
43
44bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
45 struct HashMap* map = createHashMap(numsSize);
46 for (int i = 0; i < numsSize; i++) {
47 int index = hashFindIndex(map, nums[i]);
48 if (index != -1 && i - map->values[index] <= k) {
49 destroyHashMap(map);
50 return true;
51 }
52 if (index != -1) {
53 map->values[index] = i;
54 } else {
55 hashInsert(map, nums[i], i);
56 }
57 }
58 destroyHashMap(map);
59 return false;
60}The C implementation uses a simple linear probing method to find existing entries and update them if necessary. It involves creating a custom hash map structure with keys and values to store elements and their indices. The solution updates the index of previously seen elements and continuously checks the difference between indices.
This method employs a sliding window (of length k) to automatically invalidate indices of prior numbers as the window advances through the array. The structure operates similarly to a hash set within the k-restricted scope, resulting in more direct checks and validations during index alterations.
Time Complexity: O(n*k), as each number is recalculated through prior windows.
Space Complexity: O(k), correlating with the contiguous window used.
1This sample renders Python's set, implementing an efficient sliding window. Post-exit, window size is maintained at k or below via element removal, allowing examination of relatively fresh entries, revalidating whether number exists therein.