Tag array algorithms

Duplicate Within K Distance in an Array in C: A Comprehensive Tutorial

Given an integer array and a value k, determine whether there exist two indices i and j such that arr[i] == arr[j] and |i - j| ≤ k. This problem tests your understanding of sliding windows, hash-based lookup, and time-space trade-offs. It appears frequently in coding interviews and has practical applications in duplicate detection and data validation.

This tutorial provides an in-depth exploration of detecting duplicates within K distance in C: naive nested-loop approach, hash-based sliding window approach, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[] of size n and an integer k, check if any two equal elements are within k indices of each other.

Formal condition: There exist i and j with i ≠ j such that:

• arr[i] == arr[j]
• |i - j| ≤ k

Examples:

text

Input: k = 3, arr = [1, 2, 3, 4, 1, 2, 3, 4] Output: No (duplicates are 4 apart) Input: k = 3, arr = [1, 2, 3, 1, 4, 5] Output: Yes (1 at indices 0 and 3, distance = 3) Input: k = 3, arr = [1, 2, 3, 4, 5] Output: No (no duplicates)

Why This Problem Matters

• Sliding window technique: Foundation for many array algorithms.
• Hash-based lookup: O(1) average-time membership testing.
• Time-space trade-offs: O(n×k) time vs. O(n) time with O(k) space.
• Real-world applications: Fraud detection, log analysis, network packet deduplication.
• Interview preparation: Common coding interview question.

Approaches Overview

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

For each element, compare with the next k elements.

c

#include <stdio.h> int checkDuplicatesWithinKNaive(const int arr[], int n, int k) { for (int i = 0; i < n; i++) { for (int c = 1; c <= k && (i + c) < n; c++) { if (arr[i] == arr[i + c]) { return 1; /* Found */ } } } return 0; /* Not found */ } int main(void) { int arr[] = {10, 5, 3, 4, 3, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printf("%s\n", checkDuplicatesWithinKNaive(arr, n, k) ? "Yes" : "No"); return 0; }

Expected output:

text

Yes

Time: O(n × k), Space: O(1)

Approach 2: Hash-Based Sliding Window

Maintain a hash set of the last k elements. If the current element is in the set, a duplicate exists within distance k.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 1024 /* Simple hash set with linear probing */ typedef struct { int *keys; int *occupied; int capacity; } HashSet; HashSet *createHashSet(int capacity) { HashSet *set = malloc(sizeof(HashSet)); if (set == NULL) return NULL; set->keys = malloc(capacity * sizeof(int)); set->occupied = calloc(capacity, sizeof(int)); if (set->keys == NULL || set->occupied == NULL) { free(set->keys); free(set->occupied); free(set); return NULL; } set->capacity = capacity; return set; } void freeHashSet(HashSet *set) { if (set != NULL) { free(set->keys); free(set->occupied); free(set); } } int hash(int key, int capacity) { return ((key % capacity) + capacity) % capacity; } int contains(HashSet *set, int key) { int idx = hash(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return 1; idx = (idx + 1) % set->capacity; if (idx == start) break; } return 0; } void insert(HashSet *set, int key) { int idx = hash(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return; /* Already present */ idx = (idx + 1) % set->capacity; if (idx == start) return; /* Full */ } set->keys[idx] = key; set->occupied[idx] = 1; } void removeKey(HashSet *set, int key) { int idx = hash(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) { set->occupied[idx] = 0; /* Rehash subsequent elements in cluster */ int next = (idx + 1) % set->capacity; while (set->occupied[next]) { int rehashKey = set->keys[next]; set->occupied[next] = 0; insert(set, rehashKey); next = (next + 1) % set->capacity; } return; } idx = (idx + 1) % set->capacity; if (idx == start) break; } } int checkDuplicatesWithinK(const int arr[], int n, int k) { if (n <= 1 || k < 1) return 0; int capacity = (k + 1) * 2 + 1; HashSet *set = createHashSet(capacity); if (set == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return -1; } for (int i = 0; i < n; i++) { if (contains(set, arr[i])) { freeHashSet(set); return 1; /* Duplicate within k */ } insert(set, arr[i]); /* Remove element that is now more than k away */ if (i >= k) { removeKey(set, arr[i - k]); } } freeHashSet(set); return 0; } int main(void) { int arr[] = {10, 5, 3, 4, 3, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; int result = checkDuplicatesWithinK(arr, n, k); if (result >= 0) { printf("%s\n", result ? "Yes" : "No"); } return 0; }

Expected output:

text

Yes

Time: O(n) average, Space: O(k)

Simplified Approach: Using a Sorted Sliding Window (Alternative)

For small k, a fixed-size circular buffer with linear search works well.

c

#include <stdio.h> #include <string.h> int checkDuplicatesWithinKBuffer(const int arr[], int n, int k) { if (n <= 1 || k < 1) return 0; int windowSize = (k + 1 < n) ? k + 1 : n; int *window = malloc(windowSize * sizeof(int)); if (window == NULL) return -1; int count = 0; for (int i = 0; i < n; i++) { /* Linear search in current window */ for (int j = 0; j < count; j++) { if (window[j] == arr[i]) { free(window); return 1; } } /* Add current element */ if (count < windowSize) { window[count++] = arr[i]; } else { /* Shift window left */ for (int j = 0; j < windowSize - 1; j++) { window[j] = window[j + 1]; } window[windowSize - 1] = arr[i]; } } free(window); return 0; }

Time: O(n × k), Space: O(k)

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, performance comparison, and edge cases.

Program: Duplicate Within K Distance Checker

c

/** * duplicate_within_k.c * Checks if array contains duplicates within k distance. * Compares naive and hash-based sliding window approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int checkDuplicatesNaive(const int arr[], int n, int k); int checkDuplicatesHash(const int arr[], int n, int k); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Duplicate Within K Distance Checker ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n, k; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } if (readInteger("Enter k: ", &k) != 0 || k < 1) { fprintf(stderr, "Invalid k.\n"); break; } printf("\nArray: "); printArray(arr, n); printf("k = %d\n", k); int naive = checkDuplicatesNaive(arr, n, k); int hash = checkDuplicatesHash(arr, n, k); printf("Naive result: %s\n", naive ? "Yes" : "No"); printf("Hash result: %s\n", hash ? "Yes" : "No"); printf("Verification: %s\n", (naive == hash) ? "PASS" : "FAIL"); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Naive approach: O(n * k) */ int checkDuplicatesNaive(const int arr[], int n, int k) { if (n <= 1 || k < 1) return 0; for (int i = 0; i < n; i++) { for (int c = 1; c <= k && (i + c) < n; c++) { if (arr[i] == arr[i + c]) { return 1; } } } return 0; } /* Hash-based sliding window: O(n) average, O(k) space */ typedef struct { int *keys; int *occupied; int capacity; } HashSet; HashSet *createHashSet(int capacity) { HashSet *set = malloc(sizeof(HashSet)); if (set == NULL) return NULL; set->keys = malloc(capacity * sizeof(int)); set->occupied = calloc(capacity, sizeof(int)); if (set->keys == NULL || set->occupied == NULL) { free(set->keys); free(set->occupied); free(set); return NULL; } set->capacity = capacity; return set; } void freeHashSet(HashSet *set) { if (set != NULL) { free(set->keys); free(set->occupied); free(set); } } int hashFunc(int key, int capacity) { return ((key % capacity) + capacity) % capacity; } int containsHash(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return 1; idx = (idx + 1) % set->capacity; if (idx == start) break; } return 0; } void insertHash(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return; idx = (idx + 1) % set->capacity; if (idx == start) return; } set->keys[idx] = key; set->occupied[idx] = 1; } void removeHash(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) { set->occupied[idx] = 0; /* Rehash the cluster */ int next = (idx + 1) % set->capacity; while (set->occupied[next]) { int rehashKey = set->keys[next]; set->occupied[next] = 0; insertHash(set, rehashKey); next = (next + 1) % set->capacity; } return; } idx = (idx + 1) % set->capacity; if (idx == start) break; } } int checkDuplicatesHash(const int arr[], int n, int k) { if (n <= 1 || k < 1) return 0; int capacity = (k + 1) * 2 + 1; HashSet *set = createHashSet(capacity); if (set == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return -1; } for (int i = 0; i < n; i++) { if (containsHash(set, arr[i])) { freeHashSet(set); return 1; } insertHash(set, arr[i]); if (i >= k) { removeHash(set, arr[i - k]); } } freeHashSet(set); return 0; } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates both approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {1, 2, 3, 4, 1, 2, 3, 4}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("k = 3 → Naive: %s, Hash: %s\n", checkDuplicatesNaive(arr1, n1, 3) ? "Yes" : "No", checkDuplicatesHash(arr1, n1, 3) ? "Yes" : "No"); int arr2[] = {1, 2, 3, 1, 4, 5}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("k = 3 → Naive: %s, Hash: %s\n", checkDuplicatesNaive(arr2, n2, 3) ? "Yes" : "No", checkDuplicatesHash(arr2, n2, 3) ? "Yes" : "No"); int arr3[] = {1, 2, 3, 4, 5}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); printf("k = 3 → Naive: %s, Hash: %s\n", checkDuplicatesNaive(arr3, n3, 3) ? "Yes" : "No", checkDuplicatesHash(arr3, n3, 3) ? "Yes" : "No"); int arr4[] = {10, 5, 3, 4, 3, 5, 6}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4: "); printArray(arr4, n4); printf("k = 3 → Naive: %s, Hash: %s\n", checkDuplicatesNaive(arr4, n4, 3) ? "Yes" : "No", checkDuplicatesHash(arr4, n4, 3) ? "Yes" : "No"); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000, k = 100) ===\n"); int n = 100000; int k = 100; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Fill with distinct values to avoid early exit */ for (int i = 0; i < n; i++) { arr[i] = i; } clock_t start, end; double timeTaken; /* Naive */ start = clock(); int naiveResult = checkDuplicatesNaive(arr, n, k); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (O(n*k)): Result = %s, Time = %.3f ms\n", naiveResult ? "Yes" : "No", timeTaken); /* Hash */ start = clock(); int hashResult = checkDuplicatesHash(arr, n, k); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (O(n)): Result = %s, Time = %.3f ms\n", hashResult ? "Yes" : "No", timeTaken); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Empty array */ int arr1[] = {}; printf("Case 1: Empty array\n"); printf(" Result: %s\n", checkDuplicatesHash(arr1, 0, 3) ? "Yes" : "No"); /* Case 2: Single element */ int arr2[] = {42}; printf("\nCase 2: Single element\n"); printf(" Array: "); printArray(arr2, 1); printf(" k = 3 → %s\n", checkDuplicatesHash(arr2, 1, 3) ? "Yes" : "No"); /* Case 3: Adjacent duplicates */ int arr3[] = {1, 1, 2, 3}; printf("\nCase 3: Adjacent duplicates\n"); printf(" Array: "); printArray(arr3, 4); printf(" k = 1 → %s\n", checkDuplicatesHash(arr3, 4, 1) ? "Yes" : "No"); /* Case 4: Duplicates exactly at distance k */ int arr4[] = {1, 2, 3, 1}; printf("\nCase 4: Duplicates exactly at distance k\n"); printf(" Array: "); printArray(arr4, 4); printf(" k = 3 → %s\n", checkDuplicatesHash(arr4, 4, 3) ? "Yes" : "No"); /* Case 5: k = 0 (no distance allowed) */ int arr5[] = {1, 1, 2}; printf("\nCase 5: k = 0\n"); printf(" Array: "); printArray(arr5, 3); printf(" k = 0 → %s (no duplicates possible)\n", checkDuplicatesHash(arr5, 3, 0) ? "Yes" : "No"); /* Case 6: k larger than array */ int arr6[] = {1, 2, 3, 1}; printf("\nCase 6: k > array size\n"); printf(" Array: "); printArray(arr6, 4); printf(" k = 100 → %s\n", checkDuplicatesHash(arr6, 4, 100) ? "Yes" : "No"); /* Case 7: All same elements */ int arr7[] = {5, 5, 5, 5, 5}; printf("\nCase 7: All same elements\n"); printf(" Array: "); printArray(arr7, 5); printf(" k = 1 → %s\n", checkDuplicatesHash(arr7, 5, 1) ? "Yes" : "No"); /* Case 8: Negative values */ int arr8[] = {-1, -2, -3, -1}; printf("\nCase 8: Negative values\n"); printf(" Array: "); printArray(arr8, 4); printf(" k = 3 → %s\n", checkDuplicatesHash(arr8, 4, 3) ? "Yes" : "No"); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Naive: Compares each element with the next k elements; O(n×k).
2. Hash: Maintains a hash set of the last k elements; O(n) average.

Expected Output (sample run)

text

=== Duplicate Within K Distance Checker === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [1, 2, 3, 4, 1, 2, 3, 4] k = 3 → Naive: No, Hash: No Array 2: [1, 2, 3, 1, 4, 5] k = 3 → Naive: Yes, Hash: Yes Array 3: [1, 2, 3, 4, 5] k = 3 → Naive: No, Hash: No Array 4: [10, 5, 3, 4, 3, 5, 6] k = 3 → Naive: Yes, Hash: Yes --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000, k = 100) === Naive (O(n*k)): Result = No, Time = 45.234 ms Hash (O(n)): Result = No, Time = 12.567 ms --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Empty array Result: No Case 2: Single element Array: [42] k = 3 → No Case 3: Adjacent duplicates Array: [1, 1, 2, 3] k = 1 → Yes Case 4: Duplicates exactly at distance k Array: [1, 2, 3, 1] k = 3 → Yes Case 5: k = 0 Array: [1, 1, 2] k = 0 → No (no duplicates possible) Case 6: k > array size Array: [1, 2, 3, 1] k = 100 → Yes Case 7: All same elements Array: [5, 5, 5, 5, 5] k = 1 → Yes Case 8: Negative values Array: [-1, -2, -3, -1] k = 3 → Yes

Common Pitfalls, Edge Cases & Memory Considerations

1. Off-by-One in Window Size

The window should contain exactly the last k elements (not k + 1).

c

if (i >= k) { removeHash(set, arr[i - k]); /* Correct: remove element at distance k + 1 */ }

Solution: Remove arr[i - k] when i >= k to keep window size at most k.

2. k = 0 Handling

With k = 0, only the same index can be “within distance 0”, but indices must differ.

c

if (k < 1) return 0; /* No duplicates possible */

3. k >= n Handling

If k >= n, the entire array is the window; any duplicate counts.

c

/* Handled naturally by the algorithm */

4. Empty Array

No duplicates possible.

c

if (n <= 1) return 0;

5. Hash Set Sizing

The hash set must have capacity > k to hold the window.

c

int capacity = (k + 1) * 2 + 1; /* Safe sizing */

6. Hash Collisions

Linear probing handles collisions but must be sized appropriately.

Solution: Size the table at least twice the window size.

7. Removing from Hash Set

Incorrect removal breaks the sliding window invariant.

c

removeHash(set, arr[i - k]); /* Only when i >= k */

8. Negative Values in Hash

Hash function must handle negative keys.

c

return ((key % capacity) + capacity) % capacity;

9. Memory Leaks

Free the hash set after use.

c

freeHashSet(set);

10. Memory Considerations

• Naive: O(1) extra space, O(n×k) time.
• Hash: O(k) extra space, O(n) average time.
• Hash approach preferred for large arrays and moderate k.
• Use a balanced BST or sorted array for worst-case O(n log k).

Summary & Best Practices

Detecting duplicates within K distance is a classic sliding window problem. The hash-based approach achieves O(n) average time with O(k) space.

Key Takeaways

• Naive: O(n × k) time, O(1) space.
• Hash sliding window: O(n) average time, O(k) space.
• Maintain exactly the last k elements in the window.
• Remove elements at distance k + 1 as the window slides.
• Handle k = 0, empty arrays, and single elements.

Best Practices

1. Use the hash-based approach for O(n) average time.
2. Size the hash table to at least 2 × (k + 1).
3. Handle negative keys in the hash function.
4. Check n <= 1 and k < 1 early.
5. Remove elements at i - k when i >= k.
6. Free the hash set after use.
7. Test with edge cases: empty, single, k = 0, k >= n.
8. Document window size in comments.
9. Consider k-sized sorted arrays for worst-case guarantees.
10. Profile for large arrays with varying k.

By mastering this problem, you’ll understand the sliding window technique and hash-based lookups, essential for many array and string problems.