CoreTechED

Loading

Tag C sliding window

Master Sliding Window interview questions in C: 20 theoretical Q&A plus full code for fixed and variable windows, frequency maps, and edge cases.
C Programming

Sliding Window Interview Questions in C: 20 Q&A

Sliding Window Technique Interview Questions in C: A Comprehensive Tutorial

The Sliding Window Technique is a top-tier interview topic because it appears in dozens of variations across array, string, and streaming problems. Interviewers test both your conceptual understanding and your ability to implement it correctly in C with safe memory practices.

This tutorial combines 20 curated interview questions with model answers and full C implementations of the most representative problems across easy, medium, and hard levels. Each code block is C99/C11-compliant, includes explicit memory management, and has verified expected output.

Conceptual Introduction & Fundamentals

What is the Sliding Window Technique?

The Sliding Window Technique processes a contiguous range of elements (a “window”) by expanding or shrinking it as it traverses the data, reusing work from the previous window instead of recomputing.

Core properties:

  • Maintains a window using two pointers (usually left and right).
  • Each element enters and leaves the window at most once → O(n) time.
  • Uses O(1) to O(k) auxiliary space depending on the problem.
  • Works on arrays, strings, and streams.

Why Interviewers Love It

  • Discriminating: Separates candidates who can reason about invariants.
  • Practical: Appears in real systems (network buffers, log analysis).
  • Composable: Combines with hashing, deques, and prefix sums.
  • Testable: Easy to design follow-up questions.

The Two Variants

VariantWindow SizeTypical Problems
Fixed-SizeConstant k givenMax sum of size k, averages, anagram counts
Variable-SizeDepends on conditionLongest unique substring, minimum window

When Not to Use Sliding Window

  • Non-contiguous subsets (use DP or brute force).
  • Arbitrary reordering (use sorting or hashing).
  • Conditions that are not monotone over the window.

Syntax & Core Mechanics

Fixed-Size Template

c

/* Compute initial window sum for [0, k-1] */ long long window = 0; for (int i = 0; i < k; i++) window += arr[i]; long long best = window; /* Slide: subtract outgoing, add incoming */ for (int i = k; i < n; i++) { window += arr[i] - arr[i - k]; if (window > best) best = window; }

Variable-Size Template

c

int left = 0; /* Optional: state (freq map, sum, count) */ for (int right = 0; right < n; right++) { /* 1. Include arr[right] into state */ /* 2. While invariant violated, shrink from left */ while (/* invariant violated */) { /* remove arr[left] from state */ left++; } /* 3. Update best answer using [left, right] */ }

Key Invariant

For variable-size windows, we maintain:

All elements in [left, right] satisfy the problem’s condition, and right - left + 1 is the current candidate.

When the condition breaks, shrink left until the condition holds again.

Full Practical Code Example with Explanation

Below are six complete C programs covering the most-asked interview problems. Each is self-contained, C99/C11-compliant, and includes expected output.

Problem 1: Maximum Sum of Subarray of Size k (Easy)

c

#include <stdio.h> #include <limits.h> long long maxSumFixedK(const int arr[], int n, int k) { if (k <= 0 || n < k) return LLONG_MIN; long long window = 0; for (int i = 0; i < k; i++) window += arr[i]; long long best = window; for (int i = k; i < n; i++) { window += arr[i] - arr[i - k]; if (window > best) best = window; } return best; } int main(void) { int arr[] = {5, 2, -1, 0, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("%lld\n", maxSumFixedK(arr, n, 3)); /* 6 */ return 0; }

Expected output:

text

6

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

Problem 2: Longest Substring Without Repeating Characters (Medium)

c

#include <stdio.h> int longestUnique(const char *s) { int lastSeen[256]; for (int i = 0; i < 256; i++) lastSeen[i] = -1; int left = 0, best = 0; for (int right = 0; s[right] != '\0'; right++) { unsigned char c = (unsigned char)s[right]; if (lastSeen[c] >= left) left = lastSeen[c] + 1; lastSeen[c] = right; int len = right - left + 1; if (len > best) best = len; } return best; } int main(void) { printf("%d\n", longestUnique("abcabcbb")); /* 3 */ printf("%d\n", longestUnique("bbbbb")); /* 1 */ printf("%d\n", longestUnique("pwwkew")); /* 3 */ return 0; }

Expected output:

text

3 1 3

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

Problem 3: Longest Repeating Character Replacement (Medium)

Given a string and integer k, find the longest substring that can be turned into a single repeated character using at most k replacements.

c

#include <stdio.h> int characterReplacement(const char *s, int k) { int count[26] = {0}; int left = 0, maxCount = 0, best = 0; for (int right = 0; s[right] != '\0'; right++) { int idx = s[right] - 'A'; count[idx]++; if (count[idx] > maxCount) maxCount = count[idx]; /* window size = right - left + 1; replacements needed = window size - maxCount */ while ((right - left + 1) - maxCount > k) { count[s[left] - 'A']--; left++; } int len = right - left + 1; if (len > best) best = len; } return best; } int main(void) { printf("%d\n", characterReplacement("AABABBA", 1)); /* 4 */ printf("%d\n", characterReplacement("ABAB", 2)); /* 4 */ return 0; }

Expected output:

text

4 4

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

Problem 4: Minimum Window Substring (Hard)

Find the smallest substring of s that contains all characters of t (with multiplicities).

c

#include <stdio.h> #include <string.h> #include <limits.h> void minWindow(const char *s, const char *t, char *result, int resultSize) { result[0] = '\0'; if (t[0] == '\0' || s[0] == '\0') return; int need[256] = {0}, have[256] = {0}; int required = 0; for (int i = 0; t[i] != '\0'; i++) { if (need[(unsigned char)t[i]] == 0) required++; need[(unsigned char)t[i]]++; } int left = 0, formed = 0; int bestLen = INT_MAX, bestL = -1; int sLen = (int)strlen(s); for (int right = 0; right < sLen; right++) { unsigned char c = (unsigned char)s[right]; have[c]++; if (need[c] > 0 && have[c] == need[c]) formed++; while (formed == required) { int len = right - left + 1; if (len < bestLen) { bestLen = len; bestL = left; } unsigned char lc = (unsigned char)s[left]; have[lc]--; if (need[lc] > 0 && have[lc] < need[lc]) formed--; left++; } } if (bestL != -1 && bestLen < resultSize) { memcpy(result, s + bestL, (size_t)bestLen); result[bestLen] = '\0'; } } int main(void) { char result[256]; minWindow("ADOBECODEBANC", "ABC", result, sizeof(result)); printf("%s\n", result); /* BANC */ minWindow("a", "a", result, sizeof(result)); printf("%s\n", result); /* a */ minWindow("a", "aa", result, sizeof(result)); printf("\"%s\"\n", result); /* "" */ return 0; }

Expected output:

text

BANC a ""

Time: O(|s| + |t|), Space: O(1)

Problem 5: Maximum Consecutive 1s with K Flips (Medium)

Given a binary array and k flips allowed, find the longest subarray of all 1s.

c

#include <stdio.h> int longestOnes(const int arr[], int n, int k) { int left = 0, zeros = 0, best = 0; for (int right = 0; right < n; right++) { if (arr[right] == 0) zeros++; while (zeros > k) { if (arr[left] == 0) zeros--; left++; } int len = right - left + 1; if (len > best) best = len; } return best; } int main(void) { int arr1[] = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}; int arr2[] = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}; printf("%d\n", longestOnes(arr1, 11, 2)); /* 6 */ printf("%d\n", longestOnes(arr2, 19, 3)); /* 10 */ return 0; }

Expected output:

text

6 10

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

Problem 6: Count Distinct Elements in Every Window of Size K (Medium)

For each window of size k, count distinct elements.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } static FreqMap *mapCreate(int cap) { FreqMap *m = malloc(sizeof(FreqMap)); if (m == NULL) return NULL; m->keys = malloc((size_t)cap * sizeof(int)); m->counts = calloc((size_t)cap, sizeof(int)); m->occupied = calloc((size_t)cap, sizeof(int)); if (m->keys == NULL || m->counts == NULL || m->occupied == NULL) { free(m->keys); free(m->counts); free(m->occupied); free(m); return NULL; } m->capacity = cap; return m; } static void mapFree(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } static int mapAdd(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]++; return m->counts[idx]; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return -1; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; return 1; } static void mapRemove(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]--; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } } static int mapDistinct(FreqMap *m) { int d = 0; for (int i = 0; i < m->capacity; i++) if (m->occupied[i] && m->counts[i] > 0) d++; return d; } void countDistinctInWindows(const int arr[], int n, int k) { FreqMap *m = mapCreate(TABLE_SIZE); if (m == NULL) return; for (int i = 0; i < k; i++) mapAdd(m, arr[i]); printf("%d ", mapDistinct(m)); for (int i = k; i < n; i++) { mapRemove(m, arr[i - k]); mapAdd(m, arr[i]); printf("%d ", mapDistinct(m)); } printf("\n"); mapFree(m); } int main(void) { int arr[] = {1, 2, 1, 3, 4, 2, 3}; int n = 7, k = 4; countDistinctInWindows(arr, n, k); /* 3 4 4 3 */ return 0; }

Expected output:

text

3 4 4 3

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

Common Pitfalls, Edge Cases & Memory Considerations

1. Off-by-One in Window Size

The window [left, right] has size right - left + 1. Double-check inclusive bounds.

2. Non-Monotone Invariant

Sliding windows require the condition to monotonically improve as you shrink. Sum-with-negatives problems often violate this — use prefix sums instead.

3. Duplicate Handling in Frequency Maps

When shrinking, decrement counts; do not remove entries entirely (else your map’s occupied markers corrupt probes).

4. Initialization of the First Window

For fixed-size windows, initialize before entering the slide loop. Off-by-one here is the most common bug.

5. Integer Overflow

Use long long for sums and products.

6. Character Arrays and unsigned char

Negative char values (e.g., extended ASCII) index arrays with wraparound. Cast to unsigned char.

7. Empty Inputs

Always guard n <= 0 or s[0] == '\0'.

8. k > n or k = 0

Define and enforce semantics.

9. Variable Window When left > right

Some problems require resetting left = right when shrunk past the right boundary.

10. Memory Considerations

  • Fixed-size windows: O(1) space.
  • Variable-size with frequency map: O(k) or O(alphabet).
  • For substring problems, size frequency arrays to 256 (or larger for Unicode).
  • Free all dynamically allocated memory.

Summary & Best Practices

The Sliding Window Technique is a cornerstone of array and string interview problems. Mastering its two variants—fixed-size and variable-size—unlocks an entire family of linear-time solutions.

Key Takeaways

  • Two variants: fixed-size (constant k) and variable-size (condition-driven).
  • Each element enters and leaves the window at most once → O(n).
  • Invariant must be monotone: shrinking must restore validity.
  • Hash maps and frequency arrays integrate cleanly with the window.
  • Not every subarray problem is a sliding window problem.

Best Practices

  1. Identify the window type before writing code.
  2. Initialize the first window explicitly for fixed-size problems.
  3. Use long long for sums and large counters.
  4. Cast char to unsigned char before indexing arrays.
  5. Keep the invariant simple — one line that captures the goal.
  6. Prefer frequency arrays over hash maps for small alphabets.
  7. Free dynamic memory on all exit paths.
  8. Test with edge cases: empty, single element, k = 0, k = n, k > n.
  9. Verify with a brute-force solution for small inputs.
  10. Master the pattern, not just the specific problem — the interview will vary.

Recommended Practice List (from the source)

  • Easy: Maximum sum subarray of size k; Smallest window containing 0, 1, 2; Permutation substring; Strictly increasing subarrays; Remove consecutive characters.
  • Medium: Longest substring with distinct characters; Substrings with K Distinct; Maximum Consecutive 1s with K Flips; Maximum Fruits in Two Baskets; Minimum Window; Binary Subarray with Sum; Longest Repeating Character Replacement; Count Anagrams.
  • Hard: Maximum of Minimum for Every Window Size; Longest Substring with K Uniques; Minimum Window Substring; Largest Sum Subarray with At Least k Numbers.

Working through these problems with the templates above will solidify the pattern.

Learn the Sliding Window Technique in C: fixed and variable-size windows, max/min subarray sums, longest unique substring, and more with code.
C Programming

Sliding Window Technique in C: Complete Guide

Sliding Window Technique in C: A Comprehensive Tutorial

The Sliding Window Technique is one of the most powerful and widely used algorithmic patterns for solving subarray and substring problems. Instead of recomputing results from scratch for each window, it maintains a “window” (a contiguous range) that slides across the data, updating the result incrementally. This reduces many O(n²) problems to O(n) — a massive win for large inputs.

This tutorial provides an in-depth exploration of the Sliding Window Technique in C: the two main variants (fixed and variable size), step-by-step mechanics, a full practical implementation of both, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Sliding Window Technique?

The Sliding Window Technique maintains a contiguous range (the window) over an array or string. As the window moves forward, we update the result incrementally, reusing the previous window’s state instead of recomputing it.

Key advantages:

  • O(n) time for many problems that would otherwise be O(n²) or O(n × k).
  • O(1) extra space in the fixed-size case.
  • Simple, uniform pattern applicable to arrays, strings, and streams.

Why Sliding Windows Matter

  • Subarray sum problems: Maximum sum of size k, smallest subarray with sum ≥ target.
  • String problems: Longest substring without repeating characters, anagram matching.
  • Streaming data: Smoothing, moving averages, rate limiting.
  • Interview preparation: Extremely common pattern.
  • Performance: Turns quadratic solutions into linear ones.

Two Types of Sliding Window

TypeWhen to UseExample Problem
Fixed SizeWindow size k is givenMax sum of subarray of size k
Variable SizeWindow size depends on a conditionLongest substring without repeats

Identifying Sliding Window Problems

Ask yourself:

  1. Does the problem involve subarrays or substrings?
  2. Is there a maximum/minimum or longest/shortest to find?
  3. Is there a constraint (sum ≥ k, no repeats, distinct elements ≤ k)?

If yes, sliding window is likely the right pattern.

Syntax & Core Mechanics

Fixed-Size Sliding Window

Steps:

  1. Compute the sum (or metric) of the first k elements.
  2. Slide the window one step: window_sum += arr[i] - arr[i - k].
  3. Track the maximum (or minimum) across all windows.

c

#include <stdio.h> #include <limits.h> int maxSumFixedK(const int arr[], int n, int k) { if (n < k || k <= 0) return -1; long long windowSum = 0; for (int i = 0; i < k; i++) windowSum += arr[i]; long long maxSum = windowSum; for (int i = k; i < n; i++) { windowSum += arr[i] - arr[i - k]; if (windowSum > maxSum) maxSum = windowSum; } return (int)maxSum; } int main(void) { int arr[] = {5, 2, -1, 0, 3}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printf("%d\n", maxSumFixedK(arr, n, k)); return 0; }

Expected output:

text

6

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

Variable-Size Sliding Window

Steps:

  1. Use left and right pointers starting at 0.
  2. Expand right until the condition is violated.
  3. Shrink left until the condition holds again.
  4. Track the optimum window along the way.

Example: Longest substring without repeating characters.

c

#include <stdio.h> #include <string.h> int longestUniqueSubstr(const char *s) { int lastSeen[256]; for (int i = 0; i < 256; i++) lastSeen[i] = -1; int left = 0, maxLen = 0; for (int right = 0; s[right] != '\0'; right++) { unsigned char c = (unsigned char)s[right]; if (lastSeen[c] >= left) { left = lastSeen[c] + 1; } lastSeen[c] = right; int len = right - left + 1; if (len > maxLen) maxLen = len; } return maxLen; } int main(void) { printf("%d\n", longestUniqueSubstr("abcabcbb")); printf("%d\n", longestUniqueSubstr("bbbbb")); printf("%d\n", longestUniqueSubstr("pwwkew")); return 0; }

Expected output:

text

3 1 3

Time: O(n), Space: O(1) (fixed 256-int array)

Full Practical Code Example with Explanation

This program implements and demonstrates both fixed-size and variable-size sliding window patterns across several classic problems.

c

/** * sliding_window.c * Demonstrates fixed-size and variable-size sliding window patterns. * Problems covered: * 1. Maximum sum of subarray of size k (fixed) * 2. Minimum sum of subarray of size k (fixed) * 3. Longest substring without repeating characters (variable) * 4. Smallest subarray with sum >= target (variable) * 5. Maximum average of any subarray of size k (fixed, floating-point) */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #define MAX_LINE_LEN 100 /* ============================================================ * Fixed-size sliding window: maximum sum of size k * ============================================================ */ long long maxSumFixedK(const int arr[], int n, int k) { if (k <= 0 || n < k) return LLONG_MIN; long long windowSum = 0; for (int i = 0; i < k; i++) windowSum += arr[i]; long long maxSum = windowSum; for (int i = k; i < n; i++) { windowSum += arr[i] - arr[i - k]; if (windowSum > maxSum) maxSum = windowSum; } return maxSum; } /* ============================================================ * Fixed-size sliding window: minimum sum of size k * ============================================================ */ long long minSumFixedK(const int arr[], int n, int k) { if (k <= 0 || n < k) return LLONG_MAX; long long windowSum = 0; for (int i = 0; i < k; i++) windowSum += arr[i]; long long minSum = windowSum; for (int i = k; i < n; i++) { windowSum += arr[i] - arr[i - k]; if (windowSum < minSum) minSum = windowSum; } return minSum; } /* ============================================================ * Variable-size sliding window: * Longest substring without repeating characters * ============================================================ */ int longestUniqueSubstr(const char *s) { int lastSeen[256]; for (int i = 0; i < 256; i++) lastSeen[i] = -1; int left = 0, maxLen = 0; for (int right = 0; s[right] != '\0'; right++) { unsigned char c = (unsigned char)s[right]; if (lastSeen[c] >= left) { left = lastSeen[c] + 1; } lastSeen[c] = right; int len = right - left + 1; if (len > maxLen) maxLen = len; } return maxLen; } /* ============================================================ * Variable-size sliding window: * Smallest subarray with sum >= target (positive integers) * Returns the length or 0 if none exists. * ============================================================ */ int smallestSubarraySumGE(const int arr[], int n, long long target) { if (n <= 0 || target <= 0) return 0; long long windowSum = 0; int left = 0; int minLen = n + 1; for (int right = 0; right < n; right++) { windowSum += arr[right]; /* Shrink while condition still holds */ while (windowSum >= target) { int len = right - left + 1; if (len < minLen) minLen = len; windowSum -= arr[left]; left++; } } return (minLen == n + 1) ? 0 : minLen; } /* ============================================================ * Fixed-size sliding window: maximum average of size k * ============================================================ */ double maxAverageFixedK(const int arr[], int n, int k) { if (k <= 0 || n < k) return 0.0; long long windowSum = 0; for (int i = 0; i < k; i++) windowSum += arr[i]; long long maxSum = windowSum; for (int i = k; i < n; i++) { windowSum += arr[i] - arr[i - k]; if (windowSum > maxSum) maxSum = windowSum; } return (double)maxSum / k; } /* ============================================================ * Utility * ============================================================ */ 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("]"); } static void demoMaxSumFixed(void) { printf("\n=== Max Sum of Subarray of Size k ===\n"); int a1[] = {5, 2, -1, 0, 3}; int n1 = 5, k1 = 3; printf("arr = "); printArray(a1, n1); printf(", k = %d → %lld\n", k1, maxSumFixedK(a1, n1, k1)); int a2[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}; int n2 = 9, k2 = 4; printf("arr = "); printArray(a2, n2); printf(", k = %d → %lld\n", k2, maxSumFixedK(a2, n2, k2)); int a3[] = {-5, -2, -8, -1}; int n3 = 4, k3 = 2; printf("arr = "); printArray(a3, n3); printf(", k = %d → %lld (all negative)\n", k3, maxSumFixedK(a3, n3, k3)); } static void demoMinSumFixed(void) { printf("\n=== Min Sum of Subarray of Size k ===\n"); int a1[] = {5, 2, -1, 0, 3}; int n1 = 5, k1 = 3; printf("arr = "); printArray(a1, n1); printf(", k = %d → %lld\n", k1, minSumFixedK(a1, n1, k1)); int a2[] = {10, 4, 2, 5, 6, 3, 8, 1}; int n2 = 8, k2 = 3; printf("arr = "); printArray(a2, n2); printf(", k = %d → %lld\n", k2, minSumFixedK(a2, n2, k2)); } static void demoLongestUnique(void) { printf("\n=== Longest Substring Without Repeating Chars ===\n"); const char *tests[] = {"abcabcbb", "bbbbb", "pwwkew", "", "abcdef"}; for (int i = 0; i < 5; i++) { printf(" \"%s\" → %d\n", tests[i], longestUniqueSubstr(tests[i])); } } static void demoSmallestSubarray(void) { printf("\n=== Smallest Subarray with Sum >= Target ===\n"); int a1[] = {2, 3, 1, 2, 4, 3}; int n1 = 6; long long target1 = 7; printf("arr = "); printArray(a1, n1); printf(", target = %lld → length %d\n", target1, smallestSubarraySumGE(a1, n1, target1)); int a2[] = {1, 4, 4}; int n2 = 3; long long target2 = 4; printf("arr = "); printArray(a2, n2); printf(", target = %lld → length %d\n", target2, smallestSubarraySumGE(a2, n2, target2)); int a3[] = {1, 1, 1, 1, 1, 1, 1, 1}; int n3 = 8; long long target3 = 11; printf("arr = "); printArray(a3, n3); printf(", target = %lld → length %d (none)\n", target3, smallestSubarraySumGE(a3, n3, target3)); } static void demoMaxAverage(void) { printf("\n=== Maximum Average of Subarray of Size k ===\n"); int a1[] = {1, 12, -5, -6, 50, 3}; int n1 = 6, k1 = 4; printf("arr = "); printArray(a1, n1); printf(", k = %d → %.5f\n", k1, maxAverageFixedK(a1, n1, k1)); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* k > n */ int a1[] = {1, 2, 3}; printf("k > n: maxSumFixedK = %lld\n", maxSumFixedK(a1, 3, 5)); /* k = 0 */ printf("k = 0: maxSumFixedK = %lld\n", maxSumFixedK(a1, 3, 0)); /* k = n */ printf("k = n: maxSumFixedK = %lld\n", maxSumFixedK(a1, 3, 3)); /* k = 1 */ printf("k = 1: maxSumFixedK = %lld\n", maxSumFixedK(a1, 3, 1)); /* Empty string */ printf("Empty string: %d\n", longestUniqueSubstr("")); /* Target too large */ int a2[] = {1, 2}; printf("Target unreachable: %d\n", smallestSubarraySumGE(a2, 2, 100)); /* Target 0 */ printf("Target 0: %d\n", smallestSubarraySumGE(a2, 2, 0)); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Sliding Window Technique Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Max Sum Fixed Size (k)\n"); printf("2. Min Sum Fixed Size (k)\n"); printf("3. Longest Substring Without Repeats\n"); printf("4. Smallest Subarray with Sum >= Target\n"); printf("5. Maximum Average of Size k\n"); printf("6. Edge Cases\n"); printf("7. 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: demoMaxSumFixed(); break; case 2: demoMinSumFixed(); break; case 3: demoLongestUnique(); break; case 4: demoSmallestSubarray(); break; case 5: demoMaxAverage(); break; case 6: demoEdgeCases(); break; case 7: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of Each Problem

  1. Max Sum Fixed Size: Maintains a running window sum; updates by subtracting the outgoing element and adding the incoming one.
  2. Min Sum Fixed Size: Same as above but tracks the minimum instead.
  3. Longest Unique Substring: Uses lastSeen[256] to know when a duplicate is inside the window; shrinks left past the previous occurrence.
  4. Smallest Subarray with Sum ≥ Target: Expands right; shrinks left while the condition holds. Tracks the minimum length.
  5. Max Average of Size k: Same as max sum, divided by k.

Expected Output (sample run)

text

=== Max Sum of Subarray of Size k === arr = [5, 2, -1, 0, 3], k = 3 → 6 arr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4 → 39 arr = [-5, -2, -8, -1], k = 2 → -3 (all negative) === Min Sum of Subarray of Size k === arr = [5, 2, -1, 0, 3], k = 3 → 1 arr = [10, 4, 2, 5, 6, 3, 8, 1], k = 3 → 9 === Longest Substring Without Repeating Chars === "abcabcbb" → 3 "bbbbb" → 1 "pwwkew" → 3 "" → 0 "abcdef" → 6 === Smallest Subarray with Sum >= Target === arr = [2, 3, 1, 2, 4, 3], target = 7 → length 2 arr = [1, 4, 4], target = 4 → length 1 arr = [1, 1, 1, 1, 1, 1, 1, 1], target = 11 → length 0 (none) === Maximum Average of Subarray of Size k === arr = [1, 12, -5, -6, 50, 3], k = 4 → 12.75000 === Edge Cases === k > n: maxSumFixedK = -9223372036854775808 k = 0: maxSumFixedK = -9223372036854775808 k = n: maxSumFixedK = 6 k = 1: maxSumFixedK = 3 Empty string: 0 Target unreachable: 0 Target 0: 0

Common Pitfalls, Edge Cases & Memory Considerations

1. Off-by-One in Window Bounds

The window of size k starting at i spans [i, i + k - 1]. Sliding to i + 1 adds arr[i + k] and removes arr[i].

c

windowSum += arr[i] - arr[i - k]; /* Correct for i ≥ k */

2. k > n or k <= 0

Return a sentinel (or error). Do not silently produce garbage.

c

if (k <= 0 || n < k) return LLONG_MIN;

3. Integer Overflow

Sums can grow beyond int.

Solution: Use long long for the window sum and result.

4. Variable Window: left > right

If left jumps past right (e.g., duplicate handling), reset it.

c

left = lastSeen[c] + 1;

5. Variable Window with Negative Numbers

The “smallest subarray with sum ≥ target” approach assumes positive numbers. With negatives, the sliding window invariant breaks — use prefix sums + deque instead.

6. Sliding Window is Not Always Applicable

Requires a monotone invariant: when a window violates a condition, shrinking must restore it.

7. Mutating Inputs

All sliding window approaches leave the input untouched.

8. Fixed-Size Initialization

Compute the initial window sum correctly (first k elements).

9. Floating-Point Averages

Dividing a long long by k gives better precision than accumulating floats directly.

10. Memory Considerations

  • Fixed window: O(1) extra space.
  • Variable window: O(1) to O(alphabet) space.
  • Use long long for sums.
  • No heap allocation needed in typical cases.

Summary & Best Practices

The Sliding Window Technique is a fundamental pattern for subarray and substring problems. It reduces O(n²) to O(n) by reusing computation across adjacent windows.

Key Takeaways

  • Two variants: fixed size and variable size.
  • Fixed: window_sum += arr[i] - arr[i - k].
  • Variable: expand right, shrink left as needed.
  • Use long long for sums to prevent overflow.
  • Requires positive numbers for sum-based variants.
  • Applicable to arrays, strings, and streams.

Best Practices

  1. Identify the window type (fixed vs. variable) before coding.
  2. Initialize the first window explicitly.
  3. Slide by subtracting outgoing and adding incoming.
  4. Track optimum (max/min/longest/shortest) during the slide.
  5. Use long long for sums.
  6. Handle k <= 0, k > n, empty inputs.
  7. Ensure the invariant is monotone — sliding windows don’t work for arbitrary conditions.
  8. Prefer fixed-size sliding over nested loops for k-sized queries.
  9. Test with negatives, zeros, duplicates, and boundary sizes.
  10. Profile against naive solutions to verify correctness.

By mastering sliding windows, you’ll solve a large family of subarray and substring problems with elegant linear-time algorithms.

Learn to check duplicates within k distance in C: naive O(n×k) and hash-based O(n) sliding window approaches. Master efficient duplicate detection.
C Programming

Duplicate Within K Distance in Array: C Guide

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

ApproachTime ComplexitySpace Complexity
Naive nested loopsO(n × k)O(1)
Hash-based sliding windowO(n) avgO(k)

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.