Tag pair sum

Two Sum – Pair with Given Sum in C: A Comprehensive Tutorial

The Two Sum problem is one of the most iconic coding interview questions. Given an array and a target, the task is to determine whether any two elements sum to that target. It elegantly demonstrates the progression from brute-force O(n²) to optimal O(n) using hashing, and is a gateway to many related problems like Three Sum, Four Sum, and pair-based optimization.

This tutorial provides an in-depth exploration of four approaches in C: naive pairs, sorting + binary search, sorting + two pointers, and the optimal hash set. Each approach is implemented with portable C99/C11 code, robust error handling, and complete output examples.

---

Conceptual Introduction & Fundamentals

What is Two Sum?

Given an integer array arr[] of n elements and a target value, determine if any two elements (distinct indices) sum to the target.

Examples:

text

Input: arr = [0, -1, 2, -3, 1], target = -2 Output: true (1 + (-3) = -2) Input: arr = [1, -2, 1, 0, 5], target = 0 Output: false

Why Two Sum Matters

• Foundation for k-Sum problems: Three Sum, Four Sum, and beyond.
• Algorithm comparison: Demonstrates O(n²) → O(n log n) → O(n).
• Hash set mastery: Complements and lookups in O(1) average.
• Two-pointer technique: Efficient on sorted arrays.
• Interview preparation: Asked in nearly every technical interview.

Approaches Overview

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

The Complement Trick

For each element x, the required partner is target - x. If that partner has already been seen, a pair exists. This drives the hash-set solution.

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Compare every pair.

c

#include <stdio.h> #include <stdbool.h> bool twoSumNaive(const int arr[], int n, int target) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == target) return true; } } return false; } int main(void) { int arr[] = {0, -1, 2, -3, 1}; int n = sizeof(arr) / sizeof(arr[0]); int target = -2; printf("%s\n", twoSumNaive(arr, n, target) ? "true" : "false"); return 0; }

Expected output:

text

true

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

Approach 2: Sort + Binary Search

Sort, then for each element binary-search its complement in the suffix.

c

#include <stdio.h> #include <stdlib.h> #include <stdbool.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); } static bool binarySearch(const int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return true; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return false; } bool twoSumSortBinary(const int arr_in[], int n, int target) { if (n < 2) return false; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return false; for (int i = 0; i < n; i++) arr[i] = arr_in[i]; qsort(arr, n, sizeof(int), compareInts); bool found = false; for (int i = 0; i < n - 1; i++) { int complement = target - arr[i]; if (binarySearch(arr, i + 1, n - 1, complement)) { found = true; break; } } free(arr); return found; } int main(void) { int arr[] = {0, -1, 2, -3, 1}; int n = sizeof(arr) / sizeof(arr[0]); int target = -2; printf("%s\n", twoSumSortBinary(arr, n, target) ? "true" : "false"); return 0; }

Expected output:

text

true

Time: O(n log n), Space: O(n) for copy; O(1) if in-place accepted

Approach 3: Sort + Two Pointers

After sorting, move pointers inward based on the current sum.

c

bool twoSumTwoPointers(const int arr_in[], int n, int target) { if (n < 2) return false; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return false; for (int i = 0; i < n; i++) arr[i] = arr_in[i]; qsort(arr, n, sizeof(int), compareInts); int left = 0, right = n - 1; bool found = false; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) { found = true; break; } if (sum < target) left++; else right--; } free(arr); return found; }

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

Approach 4: Hash Set (Optimal)

Insert each element into a hash set; check for the complement before inserting the current element.

c

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *occupied; int capacity; int size; } HashSet; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } HashSet *createSet(int cap) { HashSet *s = malloc(sizeof(HashSet)); if (s == NULL) return NULL; s->keys = malloc((size_t)cap * sizeof(int)); s->occupied = calloc((size_t)cap, sizeof(int)); if (s->keys == NULL || s->occupied == NULL) { free(s->keys); free(s->occupied); free(s); return NULL; } s->capacity = cap; s->size = 0; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setContains(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 1; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) break; } return 0; } int setInsert(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 0; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return -1; } s->keys[idx] = key; s->occupied[idx] = 1; s->size++; return 1; } bool twoSumHash(const int arr[], int n, int target) { if (n < 2) return false; HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return false; bool found = false; for (int i = 0; i < n; i++) { int complement = target - arr[i]; if (setContains(s, complement)) { found = true; break; } setInsert(s, arr[i]); } freeSet(s); return found; } int main(void) { int arr[] = {0, -1, 2, -3, 1}; int n = sizeof(arr) / sizeof(arr[0]); int target = -2; printf("%s\n", twoSumHash(arr, n, target) ? "true" : "false"); return 0; }

Expected output:

text

true

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

---

Full Practical Code Example with Explanation

This program compares all four approaches on multiple datasets and verifies correctness.

c

/** * two_sum.c * Determines whether any pair sums to a target. * Compares naive, sort+binary, sort+two-pointer, and hash set approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* ============================================================ * HashSet * ============================================================ */ typedef struct { int *keys; int *occupied; int capacity; int size; } HashSet; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } HashSet *createSet(int cap) { HashSet *s = malloc(sizeof(HashSet)); if (s == NULL) return NULL; s->keys = malloc((size_t)cap * sizeof(int)); s->occupied = calloc((size_t)cap, sizeof(int)); if (s->keys == NULL || s->occupied == NULL) { free(s->keys); free(s->occupied); free(s); return NULL; } s->capacity = cap; s->size = 0; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setContains(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 1; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) break; } return 0; } int setInsert(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 0; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return -1; } s->keys[idx] = key; s->occupied[idx] = 1; s->size++; return 1; } /* ============================================================ * Approaches * ============================================================ */ static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } bool twoSumNaive(const int arr[], int n, int target) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == target) return true; } } return false; } static bool binarySearchRange(const int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return true; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return false; } bool twoSumSortBinary(const int arr_in[], int n, int target) { if (n < 2) return false; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return false; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); bool found = false; for (int i = 0; i < n - 1; i++) { int complement = target - arr[i]; if (binarySearchRange(arr, i + 1, n - 1, complement)) { found = true; break; } } free(arr); return found; } bool twoSumTwoPointers(const int arr_in[], int n, int target) { if (n < 2) return false; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return false; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); int left = 0, right = n - 1; bool found = false; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) { found = true; break; } if (sum < target) left++; else right--; } free(arr); return found; } bool twoSumHash(const int arr[], int n, int target) { if (n < 2) return false; HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return false; bool found = false; for (int i = 0; i < n; i++) { int complement = target - arr[i]; if (setContains(s, complement)) { found = true; break; } setInsert(s, arr[i]); } freeSet(s); return found; } /* ============================================================ * 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[] = {0, -1, 2, -3, 1}; int a2[] = {1, -2, 1, 0, 5}; struct { int *arr; int n; int target; const char *label; } tests[] = { {a1, 5, -2, "arr=[0,-1,2,-3,1], target=-2"}, {a2, 5, 0, "arr=[1,-2,1,0,5], target=0"} }; 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"); bool r1 = twoSumNaive(tests[t].arr, tests[t].n, tests[t].target); bool r2 = twoSumSortBinary(tests[t].arr, tests[t].n, tests[t].target); bool r3 = twoSumTwoPointers(tests[t].arr, tests[t].n, tests[t].target); bool r4 = twoSumHash(tests[t].arr, tests[t].n, tests[t].target); printf(" Naive: %s\n", r1 ? "true" : "false"); printf(" Sort+Binary: %s\n", r2 ? "true" : "false"); printf(" Two Pointers: %s\n", r3 ? "true" : "false"); printf(" Hash Set: %s\n", r4 ? "true" : "false"); printf(" Verify: %s\n", (r1 == r2 && r2 == r3 && r3 == r4) ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty */ printf("Empty array, target 0: "); printf("naive=%s hash=%s\n", twoSumNaive(NULL, 0, 0) ? "true" : "false", twoSumHash(NULL, 0, 0) ? "true" : "false"); /* Single */ int a1[] = {42}; printf("Single element, target 84: "); printf("naive=%s hash=%s\n", twoSumNaive(a1, 1, 84) ? "true" : "false", twoSumHash(a1, 1, 84) ? "true" : "false"); /* Same value twice */ int a2[] = {5, 5}; printf("[5,5] target 10: naive=%s hash=%s\n", twoSumNaive(a2, 2, 10) ? "true" : "false", twoSumHash(a2, 2, 10) ? "true" : "false"); /* Same index not allowed */ int a3[] = {5}; printf("[5] target 10: naive=%s hash=%s (no pair)\n", twoSumNaive(a3, 1, 10) ? "true" : "false", twoSumHash(a3, 1, 10) ? "true" : "false"); /* Negatives */ int a4[] = {-1, -2, -3, -4}; printf("[-1,-2,-3,-4] target -5: naive=%s hash=%s\n", twoSumNaive(a4, 4, -5) ? "true" : "false", twoSumHash(a4, 4, -5) ? "true" : "false"); /* Duplicates */ int a5[] = {3, 3, 3, 3}; printf("[3,3,3,3] target 6: naive=%s hash=%s\n", twoSumNaive(a5, 4, 6) ? "true" : "false", twoSumHash(a5, 4, 6) ? "true" : "false"); /* All zeros */ int a6[] = {0, 0, 0}; printf("[0,0,0] target 0: naive=%s hash=%s\n", twoSumNaive(a6, 3, 0) ? "true" : "false", twoSumHash(a6, 3, 0) ? "true" : "false"); /* Large values (overflow) */ int a7[] = {2000000000, 2000000000}; printf("[2e9,2e9] target 4e9: (long long needed for sum)\n"); } 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(); bool r1 = twoSumNaive(sa, smallN, target); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d): %s, time=%.3f ms\n", smallN, r1 ? "true" : "false", t); start = clock(); bool r2 = twoSumSortBinary(sa, smallN, target); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sort+Binary (n=%d): %s, time=%.3f ms\n", smallN, r2 ? "true" : "false", t); start = clock(); bool r3 = twoSumTwoPointers(sa, smallN, target); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Two Pointers (n=%d): %s, time=%.3f ms\n", smallN, r3 ? "true" : "false", t); start = clock(); bool r4 = twoSumHash(sa, smallN, target); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash Set (n=%d): %s, time=%.3f ms\n", smallN, r4 ? "true" : "false", t); printf("Verify: %s\n", (r1 == r2 && r2 == r3 && r3 == r4) ? "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(); bool r5 = twoSumHash(la, largeN, 199999); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash Set (n=%d): %s, time=%.3f ms\n", largeN, r5 ? "true" : "false", t); free(la); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Two 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. 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: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of the Four Approaches

1. Naive: O(n²) pair enumeration — simple but slow.
2. Sort + Binary Search: O(n log n) — sort once, then binary-search the complement.
3. Sort + Two Pointers: O(n log n) — sort once, then use opposite-direction pointers.
4. Hash Set: O(n) average — insert-and-check complement in one pass.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: arr=[0,-1,2,-3,1], target=-2 Array: [0, -1, 2, -3, 1] Naive: true Sort+Binary: true Two Pointers: true Hash Set: true Verify: PASS Test 2: arr=[1,-2,1,0,5], target=0 Array: [1, -2, 1, 0, 5] Naive: false Sort+Binary: false Two Pointers: false Hash Set: false Verify: PASS === Edge Cases === Empty array, target 0: naive=false hash=false Single element, target 84: naive=false hash=false [5,5] target 10: naive=true hash=true [5] target 10: naive=false hash=false (no pair) [-1,-2,-3,-4] target -5: naive=true hash=true [3,3,3,3] target 6: naive=true hash=true [0,0,0] target 0: naive=true hash=true [2e9,2e9] target 4e9: (long long needed for sum) === Performance Comparison === Naive (n=3000): ..., time=~20 ms Sort+Binary (n=3000): ..., time=~1 ms Two Pointers (n=3000): ..., time=~0.8 ms Hash Set (n=3000): ..., time=~0.3 ms Verify: PASS Hash Set (n=5000000): ..., time=~300 ms

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Using the Same Element Twice

The naive loop uses j = i + 1; the hash set checks the complement before inserting the current element, preventing self-pairing.

2. Integer Overflow

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

c

if ((long long)arr[i] + arr[j] == (long long)target) /* Safer */

3. Hash Table Sizing

Undersized table causes probe failures.

Solution: Size ≥ 2× n.

4. Negative Values

Cast to unsigned int in the hash function.

5. Empty or Single-Element Arrays

No pair possible; return false early.

6. Duplicate Elements

The hash approach handles duplicates correctly — the first insertion adds one copy, the second sees the complement (itself) if 2×value == target.

7. Mutating Input

The sort-based approaches modify a copy, not the original.

8. Two Pointers Only for Sorted Arrays

Sort first; otherwise the pointer logic is invalid.

9. Early Exit

Return as soon as a pair is found; do not scan further.

10. Memory Considerations

• Naive: O(1).
• Sort-based: O(n) for the copy.
• Hash: O(n) for the set.
• Free allocated memory.

---

Summary & Best Practices

The Two Sum problem is a cornerstone of algorithmic thinking. Progressing from O(n²) to O(n) via hashing demonstrates the value of trade-off analysis.

Key Takeaways

• Pair-sum check: look for target - arr[i].
• Naive: O(n²).
• Sort + binary / two pointers: O(n log n).
• Hash set: O(n) average.
• Prevent self-pairing by checking before insertion.
• Sort-based approaches require a copy for preservation.

Best Practices

1. Use hash set for O(n) average.
2. Use sort + two pointers when memory is tight.
3. Check complement before insertion to avoid self-pairing.
4. Handle overflow via long long for large values.
5. Return early on first match.
6. Size hash table ≥ 2× n.
7. Guard against empty/single arrays.
8. Free dynamic memory.
9. Test edge cases: empty, single, duplicates, negatives, large values.
10. Profile for large inputs.

By mastering Two Sum, you’ll be ready for Three Sum, Four Sum, and many optimization problems built on pair-sum logic.