Tag C count pairs

Count All Pairs with Absolute Difference Equal to K in C: A Comprehensive Tutorial

Counting pairs with an absolute difference equal to a target k is a classic problem that combines array traversal, sorting, and hashing. It demonstrates the same set of algorithmic trade-offs as Two Sum but requires careful handling of positive and negative differences — since the absolute value can come from either direction.

This tutorial provides an in-depth exploration of three approaches in C: naive O(n²), sort + two pointers O(n log n), and hash map O(n). Each implementation uses portable C99/C11 code with robust error handling and complete output examples.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[] and a positive integer k, count pairs (i, j) with i < j such that |arr[i] - arr[j]| == k.

Examples:

text

Input: arr = [1, 4, 1, 4, 5], k = 3 Output: 4 Pairs: (1,4), (1,4), (1,4), (4,1) Input: arr = [8, 16, 12, 16, 4, 0], k = 4 Output: 5 Pairs: (8,12), (8,4), (16,12), (12,16), (4,0)

Why This Problem Matters

• Absolute value handling: Two complementary lookups per element.
• Combinatorial counting: Same-value pairs occur when k = 0.
• Hash map mastery: Frequency counting with two-pronged complement lookup.
• Algorithm comparison: O(n²) → O(n log n) → O(n).
• Interview preparation: Common coding interview question.

Key Insight

For each arr[i], a valid partner x satisfies either:

• x = arr[i] + k
• x = arr[i] - k

Checking both possibilities against a frequency map counts all pairs with absolute difference k in one pass.

Approaches Overview

Approach	Time	Space
Naive nested loops	O(n²)	O(1)
Sort + two pointers	O(n log n)	O(1) or O(n)
Hash map	O(n) average	O(n)

Same-Element Case (k = 0)

When k = 0, both complements coincide. The correct count is C(freq, 2) = freq × (freq - 1) / 2. The hash approach handles this naturally: for the second occurrence, only the +0 lookup succeeds (since -0 is the same key), so each pair is counted exactly once.

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Enumerate all pairs; test absolute difference.

c

#include <stdio.h> #include <stdlib.h> long long countPairsNaive(const int arr[], int n, int k) { long long cnt = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { long long diff = (long long)arr[i] - (long long)arr[j]; if (diff < 0) diff = -diff; if (diff == (long long)k) cnt++; } } return cnt; } int main(void) { int arr[] = {1, 4, 1, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printf("%lld\n", countPairsNaive(arr, n, k)); return 0; }

Expected output:

text

4

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

Approach 2: Sort + Two Pointers

Sort; advance i and j so that the difference matches k. Handle equal-value groups combinatorially.

c

#include <stdio.h> #include <stdlib.h> static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } long long countPairsSorted(const int arr_in[], int n, int k) { if (n < 2) return 0; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return -1; for (int i = 0; i < n; i++) arr[i] = arr_in[i]; qsort(arr, n, sizeof(int), compareInts); long long cnt = 0; int i = 0, j = 0; while (j < n) { long long diff = (long long)arr[j] - (long long)arr[i]; if (diff < k) { j++; } else if (diff > k) { i++; if (i > j) j = i; /* Keep j ≥ i */ } else { int ele1 = arr[i], ele2 = arr[j]; long long cnt1 = 0, cnt2 = 0; while (i < n && arr[i] == ele1) { i++; cnt1++; } while (j < n && arr[j] == ele2) { j++; cnt2++; } if (ele1 == ele2) cnt += cnt1 * (cnt1 - 1) / 2; else cnt += cnt1 * cnt2; } } free(arr); return cnt; } int main(void) { int arr[] = {1, 4, 1, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printf("%lld\n", countPairsSorted(arr, n, k)); return 0; }

Expected output:

text

4

Time: O(n log n), Space: O(n) for copy

Approach 3: Hash Map (Optimal)

For each element, look up both arr[i] + k and arr[i] - k, then insert.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 8192 typedef struct { int *keys; long long *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } FreqMap *createMap(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(long long)); 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; } void freeMap(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } long long mapGet(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) return m->counts[idx]; idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) break; } return 0; } void mapIncrement(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; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; } long long countPairsHash(const int arr[], int n, int k) { if (n < 2) return 0; FreqMap *m = createMap(TABLE_SIZE); if (m == NULL) return -1; long long cnt = 0; for (int i = 0; i < n; i++) { /* Partner greater by k */ cnt += mapGet(m, arr[i] + k); /* Partner smaller by k */ cnt += mapGet(m, arr[i] - k); /* Now record current element */ mapIncrement(m, arr[i]); } freeMap(m); return cnt; } int main(void) { int arr[] = {1, 4, 1, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printf("%lld\n", countPairsHash(arr, n, k)); return 0; }

Expected output:

text

4

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

Handling k = 0

When k == 0, both lookups are identical to arr[i]. The frequency counts prior occurrences, yielding exactly C(freq, 2) automatically. No special-casing required.

---

Full Practical Code Example with Explanation

This program compares all three approaches and exercises edge cases including k = 0, negatives, and large datasets.

c

/** * count_pairs_diff_k.c * Counts pairs with |arr[i] - arr[j]| == k. * Compares naive, sort+two-pointer, and hash map approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* ============================================================ * FreqMap * ============================================================ */ typedef struct { int *keys; long long *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } FreqMap *createMap(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(long long)); 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; } void freeMap(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } long long mapGet(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) return m->counts[idx]; idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) break; } return 0; } void mapIncrement(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; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; } /* ============================================================ * Approaches * ============================================================ */ long long countPairsNaive(const int arr[], int n, int k) { long long cnt = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { long long diff = (long long)arr[i] - (long long)arr[j]; if (diff < 0) diff = -diff; if (diff == (long long)k) cnt++; } } return cnt; } static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } long long countPairsSorted(const int arr_in[], int n, int k) { if (n < 2) return 0; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return -1; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); long long cnt = 0; int i = 0, j = 0; while (j < n) { long long diff = (long long)arr[j] - (long long)arr[i]; if (diff < k) { j++; } else if (diff > k) { i++; if (i > j) j = i; } else { int ele1 = arr[i], ele2 = arr[j]; long long cnt1 = 0, cnt2 = 0; while (i < n && arr[i] == ele1) { i++; cnt1++; } while (j < n && arr[j] == ele2) { j++; cnt2++; } if (ele1 == ele2) cnt += cnt1 * (cnt1 - 1) / 2; else cnt += cnt1 * cnt2; } } free(arr); return cnt; } long long countPairsHash(const int arr[], int n, int k) { if (n < 2) return 0; FreqMap *m = createMap(TABLE_SIZE); if (m == NULL) return -1; long long cnt = 0; for (int i = 0; i < n; i++) { cnt += mapGet(m, arr[i] + k); cnt += mapGet(m, arr[i] - k); mapIncrement(m, arr[i]); } freeMap(m); return cnt; } /* ============================================================ * 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 demoBasic(void) { printf("\n=== Sample Arrays ===\n"); int a1[] = {1, 4, 1, 4, 5}; int a2[] = {8, 16, 12, 16, 4, 0}; struct { int *arr; int n; int k; const char *label; } tests[] = { {a1, 5, 3, "arr=[1,4,1,4,5], k=3"}, {a2, 6, 4, "arr=[8,16,12,16,4,0], k=4"} }; int nt = sizeof(tests) / sizeof(tests[0]); for (int t = 0; t < nt; t++) { printf("\nTest %d: %s\n", t + 1, tests[t].label); printf(" Array: "); printArray(tests[t].arr, tests[t].n); printf("\n"); long long r1 = countPairsNaive(tests[t].arr, tests[t].n, tests[t].k); long long r2 = countPairsSorted(tests[t].arr, tests[t].n, tests[t].k); long long r3 = countPairsHash(tests[t].arr, tests[t].n, tests[t].k); printf(" Naive: %lld\n Sorted: %lld\n Hash: %lld\n", r1, r2, r3); printf(" Verify: %s\n", (r1 == r2 && r2 == r3) ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty */ printf("Empty array: naive=%lld, sorted=%lld, hash=%lld\n", countPairsNaive(NULL, 0, 1), countPairsSorted(NULL, 0, 1), countPairsHash(NULL, 0, 1)); /* Single */ int a1[] = {42}; printf("Single element: %lld / %lld / %lld\n", countPairsNaive(a1, 1, 5), countPairsSorted(a1, 1, 5), countPairsHash(a1, 1, 5)); /* Two equal, k=0 */ int a2[] = {5, 5}; printf("[5,5] k=0: %lld / %lld / %lld (expect 1)\n", countPairsNaive(a2, 2, 0), countPairsSorted(a2, 2, 0), countPairsHash(a2, 2, 0)); /* All same, k=0, freq=6 → C(6,2)=15 */ int a3[] = {7, 7, 7, 7, 7, 7}; printf("[7×6] k=0: %lld / %lld / %lld (expect 15)\n", countPairsNaive(a3, 6, 0), countPairsSorted(a3, 6, 0), countPairsHash(a3, 6, 0)); /* No pairs */ int a4[] = {1, 2, 3}; printf("[1,2,3] k=10: %lld / %lld / %lld\n", countPairsNaive(a4, 3, 10), countPairsSorted(a4, 3, 10), countPairsHash(a4, 3, 10)); /* Negatives */ int a5[] = {-1, -4, -1, -4, -5}; printf("[-1,-4,-1,-4,-5] k=3: %lld / %lld / %lld\n", countPairsNaive(a5, 5, 3), countPairsSorted(a5, 5, 3), countPairsHash(a5, 5, 3)); /* Zero and positives */ int a6[] = {0, 3, 0, 3}; printf("[0,3,0,3] k=3: %lld / %lld / %lld (expect 4)\n", countPairsNaive(a6, 4, 3), countPairsSorted(a6, 4, 3), countPairsHash(a6, 4, 3)); /* Large values, k small */ int a7[] = {1000000000, 1000000001, 999999999}; printf("Large values k=1: %lld / %lld / %lld\n", countPairsNaive(a7, 3, 1), countPairsSorted(a7, 3, 1), countPairsHash(a7, 3, 1)); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); /* Naive small */ int smallN = 3000; int *sa = malloc((size_t)smallN * sizeof(int)); if (sa == NULL) return; srand(42); for (int i = 0; i < smallN; i++) sa[i] = (rand() % 2000) - 1000; int k = 500; clock_t start, end; double t; start = clock(); long long r1 = countPairsNaive(sa, smallN, k); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d): result=%lld, time=%.3f ms\n", smallN, r1, t); start = clock(); long long r2 = countPairsSorted(sa, smallN, k); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted (n=%d): result=%lld, time=%.3f ms\n", smallN, r2, t); start = clock(); long long r3 = countPairsHash(sa, smallN, k); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): result=%lld, time=%.3f ms\n", smallN, r3, t); printf("Verify: %s\n", (r1 == r2 && r2 == r3) ? "PASS" : "FAIL"); free(sa); /* Large hash */ int largeN = 5000000; int *la = malloc((size_t)largeN * sizeof(int)); if (la == NULL) return; for (int i = 0; i < largeN; i++) la[i] = rand() % 100000; start = clock(); long long r4 = countPairsHash(la, largeN, 500); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d, k=500): result=%lld, time=%.3f ms\n", largeN, r4, t); free(la); } static 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; } static void demoInteractive(void) { int n, k; if (readInteger("Enter array size (1-10000): ", &n) != 0 || n < 1 || n > 10000) { printf("Invalid size.\n"); return; } int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return; for (int i = 0; i < n; i++) { char prompt[40]; snprintf(prompt, sizeof(prompt), " arr[%d]: ", i); if (readInteger(prompt, &arr[i]) != 0) { printf("Invalid value.\n"); free(arr); return; } } if (readInteger("Enter k (non-negative): ", &k) != 0 || k < 0) { printf("Invalid k.\n"); free(arr); return; } printf("\nArray: "); printArray(arr, n); printf("\n"); printf("Pair count: %lld\n", countPairsHash(arr, n, k)); free(arr); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Count Pairs with Absolute Difference K Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Edge Cases\n"); printf("3. Performance Comparison\n"); printf("4. Interactive\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: demoBasic(); break; case 2: demoEdgeCases(); break; case 3: performanceTest(); break; case 4: demoInteractive(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of the Approaches

1. Naive: Compute |arr[i] - arr[j]| for all pairs. Simple, quadratic.
2. Sorted + Two Pointers: After sorting, use sliding pointers so the difference is monotone.
3. Hash Map: For each element, look up arr[i] + k and arr[i] - k before insertion.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: arr=[1,4,1,4,5], k=3 Array: [1, 4, 1, 4, 5] Naive: 4 Sorted: 4 Hash: 4 Verify: PASS Test 2: arr=[8,16,12,16,4,0], k=4 Array: [8, 16, 12, 16, 4, 0] Naive: 5 Sorted: 5 Hash: 5 Verify: PASS === Edge Cases === Empty array: naive=0, sorted=0, hash=0 Single element: 0 / 0 / 0 [5,5] k=0: 1 / 1 / 1 (expect 1) [7×6] k=0: 15 / 15 / 15 (expect 15) [1,2,3] k=10: 0 / 0 / 0 [-1,-4,-1,-4,-5] k=3: 4 / 4 / 4 [0,3,0,3] k=3: 4 / 4 / 4 (expect 4) Large values k=1: 2 / 2 / 2

---

Common Pitfalls, Edge Cases & Memory Considerations

1. int Overflow in the Count

For large arrays with many duplicates, the count may exceed int.

Solution: Use long long for the count.

2. Integer Overflow in Difference

arr[i] - arr[j] can overflow int.

Solution: Cast operands to long long before subtracting.

3. Double Counting in Hash Map

Checking +k and -k looks redundant, but each finds a different pair orientation. Only pairs where the current element is the larger (via -k) or smaller (via +k) side are counted once each.

4. k = 0 Handling

Both lookups target arr[i]. The frequency counts prior occurrences; each pair is counted once, yielding C(freq, 2) automatically.

5. Negative k

The problem specifies k is positive; still guard against negative input.

6. Hash Table Sizing

Undersized table → probe failures.

Solution: Size ≥ 2× n.

7. Negatives Keys

Cast to unsigned int in the hash function.

8. Two-Pointer Invariant

Keep j ≥ i when moving i.

c

if (i > j) j = i;

9. Mutating Inputs in Sort

Copy before sorting if preservation is needed.

10. Memory Considerations

• Naive: O(1).
• Sorted: O(n) for the copy.
• Hash: O(n) for the frequency map.
• Free all dynamic allocations.

---

Summary & Best Practices

Counting pairs with absolute difference k is a classic problem with three clean solutions. The hash-map approach is optimal at O(n) average time using two-pronged complement lookup.

Key Takeaways

• Pair condition: |arr[i] - arr[j]| == k.
• Naive: O(n²).
• Sort + two pointers: O(n log n), combinatorial counting for equal groups.
• Hash map: O(n) average with two complement lookups per element.
• k = 0 handled naturally by frequency counting.
• Use long long for sums and counts.

Best Practices

1. Use the hash map for O(n) average performance.
2. Use long long for the count and differences.
3. Look up both arr[i] + k and arr[i] - k before insertion.
4. Cast negative keys to unsigned int.
5. Size hash tables ≥ 2× n.
6. Handle k = 0 via natural frequency counting.
7. Keep j ≥ i in the sorted two-pointer approach.
8. Free allocated memory.
9. Test edge cases: empty, single, k = 0, negatives, large values.
10. Profile for large inputs.

By mastering this problem, you’ll be equipped for count-based pair problems involving absolute value, distance, and metric-based lookups.