Tag two sum

2 Sum – Count Pairs with Given Sum in C: A Comprehensive Tutorial

Counting the number of pairs in an array whose sum equals a target value is a classic problem that extends the well-known Two Sum. Instead of merely checking whether a pair exists, we must count all valid pairs, including cases where elements repeat.

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 is implemented with portable C99/C11 code, robust error handling, and complete output examples.

Conceptual Introduction & Fundamentals

What is the Problem?

Given an integer array arr[] and a target value, count the number of distinct index pairs (i, j) with i < j such that arr[i] + arr[j] == target.

Examples:

text

Input: arr = [1, 5, 7, -1, 5], target = 6 Output: 3 Explanation: (1,5), (7,-1), (1,5) Input: arr = [1, 1, 1, 1], target = 2 Output: 6 Explanation: 4C2 = 6 unordered pairs of identical elements Input: arr = [10, 12, 10, 15, -1], target = 125 Output: 0

Why This Problem Matters

• Counting combinatorics: Same-value pairs require the formula C(k, 2) = k(k-1)/2.
• Hash map mastery: Frequency-based counting in one pass.
• Algorithm comparison: O(n²) → O(n log n) → O(n).
• Real-world relevance: Analytics, matching systems, and graph edge counting.
• Interview preparation: Common coding interview question.

Approaches Overview

The Same-Element Formula

When both elements are equal (2 × value == target), the number of pairs is C(freq, 2) = freq × (freq - 1) / 2.

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Enumerate all pairs (i, j) with i < j.

c

#include <stdio.h> int countPairsNaive(const int arr[], int n, int target) { int cnt = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == target) cnt++; } } return cnt; } int main(void) { int arr[] = {1, 5, 7, -1, 5}; int n = sizeof(arr) / sizeof(arr[0]); int target = 6; printf("%d\n", countPairsNaive(arr, n, target)); return 0; }

Expected output:

text

3

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

Approach 2: Sort + Two Pointers

Sort the array; move left/right inward; handle groups of equal values.

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 target) { 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 res = 0; int left = 0, right = n - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { int ele1 = arr[left], ele2 = arr[right]; long long cnt1 = 0, cnt2 = 0; while (left <= right && arr[left] == ele1) { left++; cnt1++; } while (left <= right && arr[right] == ele2) { right--; cnt2++; } if (ele1 == ele2) { res += cnt1 * (cnt1 - 1) / 2; /* C(cnt1, 2) */ } else { res += cnt1 * cnt2; } } } free(arr); return res; } int main(void) { int arr[] = {1, 5, 7, -1, 5}; int n = sizeof(arr) / sizeof(arr[0]); int target = 6; printf("%lld\n", countPairsSorted(arr, n, target)); return 0; }

Expected output:

text

3

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

Approach 3: Hash Map

Insert elements as you go, checking for the complement before insertion.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 8192 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; } 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(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; } 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 target) { if (n < 2) return 0; FreqMap *freq = createMap(TABLE_SIZE); if (freq == NULL) return -1; long long cnt = 0; for (int i = 0; i < n; i++) { long long c = mapGet(freq, target - arr[i]); cnt += c; mapIncrement(freq, arr[i]); } freeMap(freq); return cnt; } int main(void) { int arr[] = {1, 5, 7, -1, 5}; int n = sizeof(arr) / sizeof(arr[0]); int target = 6; printf("%lld\n", countPairsHash(arr, n, target)); return 0; }

Expected output:

text

3

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

Full Practical Code Example with Explanation

This program compares all three approaches and exercises edge cases including large values and many duplicates.

c

/** * count_pairs_sum.c * Counts pairs in an array whose sum equals a target. * Compares naive, sort+two-pointers, 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 target) { long long cnt = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if ((long long)arr[i] + arr[j] == (long long)target) 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 target) { 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 res = 0; int left = 0, right = n - 1; while (left < right) { long long sum = (long long)arr[left] + arr[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { int ele1 = arr[left], ele2 = arr[right]; long long cnt1 = 0, cnt2 = 0; while (left <= right && arr[left] == ele1) { left++; cnt1++; } while (left <= right && arr[right] == ele2) { right--; cnt2++; } if (ele1 == ele2) res += cnt1 * (cnt1 - 1) / 2; else res += cnt1 * cnt2; } } free(arr); return res; } long long countPairsHash(const int arr[], int n, int target) { 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, target - arr[i]); 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, 5, 7, -1, 5}; int a2[] = {1, 1, 1, 1}; int a3[] = {10, 12, 10, 15, -1}; struct { int *arr; int n; int target; const char *label; } tests[] = { {a1, 5, 6, "arr=[1,5,7,-1,5], target=6"}, {a2, 4, 2, "arr=[1,1,1,1], target=2"}, {a3, 5, 125, "arr=[10,12,10,15,-1], target=125"} }; 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].target); long long r2 = countPairsSorted(tests[t].arr, tests[t].n, tests[t].target); long long r3 = countPairsHash(tests[t].arr, tests[t].n, tests[t].target); 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, 0), countPairsSorted(NULL, 0, 0), countPairsHash(NULL, 0, 0)); /* Single */ int a1[] = {5}; printf("Single element target 10: naive=%lld, sorted=%lld, hash=%lld\n", countPairsNaive(a1, 1, 10), countPairsSorted(a1, 1, 10), countPairsHash(a1, 1, 10)); /* Two equal */ int a2[] = {5, 5}; printf("[5,5] target 10: %lld / %lld / %lld\n", countPairsNaive(a2, 2, 10), countPairsSorted(a2, 2, 10), countPairsHash(a2, 2, 10)); /* All same, large */ int a3[] = {7, 7, 7, 7, 7, 7}; printf("[7×6] target 14: %lld / %lld / %lld (expect C(6,2)=15)\n", countPairsNaive(a3, 6, 14), countPairsSorted(a3, 6, 14), countPairsHash(a3, 6, 14)); /* Negatives */ int a4[] = {-1, -2, -3, -4}; printf("[-1,-2,-3,-4] target -5: %lld / %lld / %lld\n", countPairsNaive(a4, 4, -5), countPairsSorted(a4, 4, -5), countPairsHash(a4, 4, -5)); /* Mixed */ int a5[] = {3, 5, 2, 4, 3, 5, 3}; printf("[3,5,2,4,3,5,3] target 8: %lld / %lld / %lld\n", countPairsNaive(a5, 7, 8), countPairsSorted(a5, 7, 8), countPairsHash(a5, 7, 8)); /* No pair */ int a6[] = {1, 2, 3}; printf("[1,2,3] target 100: %lld / %lld / %lld\n", countPairsNaive(a6, 3, 100), countPairsSorted(a6, 3, 100), countPairsHash(a6, 3, 100)); /* Large values (overflow test) */ int a7[] = {2000000000, 2000000000, -2000000000, -2000000000}; printf("Large values target 0: %lld / %lld / %lld\n", countPairsNaive(a7, 4, 0), countPairsSorted(a7, 4, 0), countPairsHash(a7, 4, 0)); } 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 target = 1234; clock_t start, end; double t; start = clock(); long long r1 = countPairsNaive(sa, smallN, target); 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, target); 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, target); 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, 199999); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): 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; 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; } } int target; if (readInteger("Enter target: ", &target) != 0) { printf("Invalid target.\n"); free(arr); return; } printf("\nArray: "); printArray(arr, n); printf("\n"); printf("Pair count: %lld\n", countPairsHash(arr, n, target)); free(arr); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Count Pairs With Given Sum 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: Enumerate all n(n-1)/2 pairs. Straightforward but quadratic.
2. Sorted + Two Pointers: Sort and move pointers inward; count runs of equal values and use combinatorial formulas.
3. Hash Map: For each element, count how many times its complement has already been seen; insert the current element.

Expected Output (sample run)

text

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

Common Pitfalls, Edge Cases & Memory Considerations

1. Using int for the Count

For large arrays with many duplicates, the count can exceed int (e.g., n = 100000 with all equal values → ~5×10⁹ pairs).

Solution: Use long long for the count.

2. Integer Overflow in Sum

arr[i] + arr[j] can overflow for large values.

Solution: Cast to long long before adding.

c

if ((long long)arr[i] + arr[j] == (long long)target) ...

3. Counting Self-Pairs

The hash map approach checks the complement before inserting the current element, ensuring i < j.

4. Same-Element Pairs

When 2 × value == target, use C(freq, 2) = freq × (freq - 1) / 2 in the sorted approach, or let the hash map naturally accumulate matches (since the first insertion precedes the second lookup).

5. Duplicate Keys in Hash

The hash map must store frequencies, not just presence.

6. Hash Table Sizing

Undersized table → probe failures.

Solution: Size ≥ 2× n.

7. Negative Values

Cast to unsigned int in the hash function.

8. Mutating Inputs

The sorted approach copies inputs; this preserves originals.

9. Empty or Single-Element Arrays

No pairs possible; return 0 early.

10. Memory Considerations

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

Summary & Best Practices

The count-pairs-sum problem is the natural extension of Two Sum. It requires frequency tracking rather than mere existence.

Key Takeaways

• Count all index pairs (i, j), i < j, with arr[i] + arr[j] == target.
• Naive: O(n²).
• Sort + two pointers: O(n log n) with combinatorial counting.
• Hash map: O(n) average using complement lookup.
• Use long long for both sum and count.
• Handle same-element pairs with C(freq, 2).

Best Practices

1. Use the hash map for O(n) average performance.
2. Count with long long to prevent overflow.
3. Sum with long long to prevent overflow.
4. Check complement before insertion to avoid self-pairs.
5. Handle same-element pairs with C(freq, 2) in sorted approach.
6. Size hash tables ≥ 2× n.
7. Cast negative keys to unsigned int.
8. Copy inputs before sorting when preservation is needed.
9. Free allocated memory.
10. Test edge cases: empty, single, all-same, negatives, large values.

By mastering this problem, you’ll be well prepared for Three Sum, Four Sum, and other pair-counting variants.