Tag sorting

Missing Elements in Range in C: A Comprehensive Tutorial

Given an array and a numeric range [low, high], the task is to find all integers inside that range that are not present in the array, returned in ascending order. This problem appears in data validation, gap detection, and range-based analytics, and it demonstrates a clear progression from brute force to optimal O(n + r) time.

This tutorial explores four approaches in C: naive linear scan, sorted two-pointer, hash set, and boolean array. Each is implemented with portable C99/C11 code and complete output examples.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an integer array arr[] and a range [low, high], output every integer in [low, high] that is not in arr[], in ascending order.

Examples:

text

Input: arr = [10, 12, 11, 15], low = 10, high = 15 Output: [13, 14] Input: arr = [1, 4, 11, 51, 15], low = 50, high = 55 Output: [50, 52, 53, 54, 55]

Why This Problem Matters

• Set membership: Foundation for range queries and gap detection.
• Time-space trade-offs: O(r × n) → O(n log n) → O(n + r).
• Hash vs boolean array: Choosing between sparse and dense representations.
• Real-world use: Missing sequence IDs, invoice gaps, license plate ranges.
• Interview preparation: Common coding interview question.

Notation

Let n = length(arr) and r = high - low + 1.

Approaches Overview

Approach	Time	Space
Naive linear scan	O(r × n)	O(r) for result
Sorting + two pointers	O(n log n + r)	O(1) or O(n)
Hash set	O(n + r) avg	O(n)
Boolean array	O(n + r)	O(r)

---

Syntax & Core Mechanics

Approach 1: Naive Linear Scan

For each number in [low, high], scan the array to check presence.

c

#include <stdio.h> #include <stdlib.h> int *missingRangeNaive(const int arr[], int n, int low, int high, int *outSize) { if (low > high) { *outSize = 0; return NULL; } int r = high - low + 1; int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { *outSize = 0; return NULL; } int k = 0; for (int x = low; x <= high; x++) { int found = 0; for (int i = 0; i < n; i++) { if (arr[i] == x) { found = 1; break; } } if (!found) res[k++] = x; } *outSize = k; return res; } int main(void) { int arr[] = {1, 4, 11, 51, 15}; int n = sizeof(arr) / sizeof(arr[0]); int low = 50, high = 55, size = 0; int *res = missingRangeNaive(arr, n, low, high, &size); printf("["); for (int i = 0; i < size; i++) { printf("%d", res[i]); if (i < size - 1) printf(", "); } printf("]\n"); free(res); return 0; }

Expected output:

text

[50, 52, 53, 54, 55]

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

Approach 2: Sort + Two Pointers

Sort the array; scan the range while advancing a pointer.

c

#include <stdio.h> #include <stdlib.h> #include <string.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); } int *missingRangeSorted(const int arr_in[], int n, int low, int high, int *outSize) { if (low > high) { *outSize = 0; return NULL; } int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL && n > 0) { *outSize = 0; return NULL; } if (n > 0) memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); int r = high - low + 1; int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { free(arr); *outSize = 0; return NULL; } int k = 0, i = 0; for (int x = low; x <= high; x++) { while (i < n && arr[i] < x) i++; if (i == n || arr[i] != x) res[k++] = x; } free(arr); *outSize = k; return res; } int main(void) { int arr[] = {1, 4, 11, 51, 15}; int n = sizeof(arr) / sizeof(arr[0]); int low = 50, high = 55, size = 0; int *res = missingRangeSorted(arr, n, low, high, &size); printf("["); for (int i = 0; i < size; i++) { printf("%d", res[i]); if (i < size - 1) printf(", "); } printf("]\n"); free(res); return 0; }

Expected output:

text

[50, 52, 53, 54, 55]

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

Approach 3: Hash Set

Insert all array values into a hash set; check each range number in O(1).

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 8192 typedef struct { int *keys; int *occupied; int capacity; } 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; 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; } void 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; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return; } s->keys[idx] = key; s->occupied[idx] = 1; } int *missingRangeHash(const int arr[], int n, int low, int high, int *outSize) { if (low > high) { *outSize = 0; return NULL; } HashSet *s = createSet(TABLE_SIZE); if (s == NULL) { *outSize = 0; return NULL; } for (int i = 0; i < n; i++) setInsert(s, arr[i]); int r = high - low + 1; int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { freeSet(s); *outSize = 0; return NULL; } int k = 0; for (int x = low; x <= high; x++) { if (!setContains(s, x)) res[k++] = x; } freeSet(s); *outSize = k; return res; } int main(void) { int arr[] = {1, 4, 11, 51, 15}; int n = sizeof(arr) / sizeof(arr[0]); int low = 50, high = 55, size = 0; int *res = missingRangeHash(arr, n, low, high, &size); printf("["); for (int i = 0; i < size; i++) { printf("%d", res[i]); if (i < size - 1) printf(", "); } printf("]\n"); free(res); return 0; }

Expected output:

text

[50, 52, 53, 54, 55]

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

Approach 4: Boolean Array (Dense Range)

Allocate r booleans. Mark array elements within [low, high]; then scan.

c

int *missingRangeBool(const int arr[], int n, int low, int high, int *outSize) { if (low > high) { *outSize = 0; return NULL; } int r = high - low + 1; unsigned char *present = calloc((size_t)r, sizeof(unsigned char)); if (present == NULL) { *outSize = 0; return NULL; } for (int i = 0; i < n; i++) { if (arr[i] >= low && arr[i] <= high) { present[arr[i] - low] = 1; } } int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { free(present); *outSize = 0; return NULL; } int k = 0; for (int i = 0; i < r; i++) { if (!present[i]) res[k++] = low + i; } free(present); *outSize = k; return res; }

Time: O(n + r), Space: O(r)

Recommendation: Prefer the boolean array when r is modest (e.g., ≤ 10⁷). Use the hash set when r is huge but n is small.

---

Full Practical Code Example with Explanation

This program implements all four approaches and verifies they agree.

c

/** * missing_in_range.c * Finds integers in [low, high] not present in arr[]. * Compares naive, sorted, hash set, and boolean-array 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 /* ============================================================ * HashSet * ============================================================ */ typedef struct { int *keys; int *occupied; int capacity; } 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; 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; } void 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; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return; } s->keys[idx] = key; s->occupied[idx] = 1; } /* ============================================================ * Approaches * ============================================================ */ int *missingRangeNaive(const int arr[], int n, int low, int high, int *outSize) { *outSize = 0; if (low > high) return NULL; int r = high - low + 1; int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) return NULL; int k = 0; for (int x = low; x <= high; x++) { int found = 0; for (int i = 0; i < n; i++) { if (arr[i] == x) { found = 1; break; } } if (!found) res[k++] = x; } *outSize = k; return res; } static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } int *missingRangeSorted(const int arr_in[], int n, int low, int high, int *outSize) { *outSize = 0; if (low > high) return NULL; int *arr = NULL; if (n > 0) { arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return NULL; memcpy(arr, arr_in, (size_t)n * sizeof(int)); } qsort(arr, n, sizeof(int), compareInts); int r = high - low + 1; int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { free(arr); return NULL; } int k = 0, i = 0; for (int x = low; x <= high; x++) { while (i < n && arr[i] < x) i++; if (i == n || arr[i] != x) res[k++] = x; } free(arr); *outSize = k; return res; } int *missingRangeHash(const int arr[], int n, int low, int high, int *outSize) { *outSize = 0; if (low > high) return NULL; HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return NULL; for (int i = 0; i < n; i++) setInsert(s, arr[i]); int r = high - low + 1; int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { freeSet(s); return NULL; } int k = 0; for (int x = low; x <= high; x++) { if (!setContains(s, x)) res[k++] = x; } freeSet(s); *outSize = k; return res; } int *missingRangeBool(const int arr[], int n, int low, int high, int *outSize) { *outSize = 0; if (low > high) return NULL; int r = high - low + 1; unsigned char *present = calloc((size_t)r, sizeof(unsigned char)); if (present == NULL) return NULL; for (int i = 0; i < n; i++) { if (arr[i] >= low && arr[i] <= high) { present[arr[i] - low] = 1; } } int *res = malloc((size_t)r * sizeof(int)); if (res == NULL) { free(present); return NULL; } int k = 0; for (int i = 0; i < r; i++) { if (!present[i]) res[k++] = low + i; } free(present); *outSize = k; return res; } /* ============================================================ * 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[] = {10, 12, 11, 15}; int a2[] = {1, 4, 11, 51, 15}; struct { int *arr; int n; int low; int high; const char *label; } tests[] = { {a1, 4, 10, 15, "arr=[10,12,11,15], range=[10,15]"}, {a2, 5, 50, 55, "arr=[1,4,11,51,15], range=[50,55]"} }; 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"); int s1, s2, s3, s4; int *r1 = missingRangeNaive(tests[t].arr, tests[t].n, tests[t].low, tests[t].high, &s1); int *r2 = missingRangeSorted(tests[t].arr, tests[t].n, tests[t].low, tests[t].high, &s2); int *r3 = missingRangeHash(tests[t].arr, tests[t].n, tests[t].low, tests[t].high, &s3); int *r4 = missingRangeBool(tests[t].arr, tests[t].n, tests[t].low, tests[t].high, &s4); printf(" Naive: "); printArray(r1, s1); printf("\n"); printf(" Sorted: "); printArray(r2, s2); printf("\n"); printf(" Hash: "); printArray(r3, s3); printf("\n"); printf(" Boolean: "); printArray(r4, s4); printf("\n"); int ok = (s1 == s2 && s2 == s3 && s3 == s4); if (ok) { for (int i = 0; i < s1; i++) { if (r1[i] != r2[i] || r2[i] != r3[i] || r3[i] != r4[i]) { ok = 0; break; } } } printf(" Verify: %s\n", ok ? "PASS" : "FAIL"); free(r1); free(r2); free(r3); free(r4); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int size = 0; /* Empty array, non-empty range */ int *r = missingRangeHash(NULL, 0, 1, 5, &size); printf("Empty arr, [1..5]: "); printArray(r, size); printf("\n"); free(r); /* Empty range (low > high) */ int a1[] = {1, 2, 3}; r = missingRangeHash(a1, 3, 5, 4, &size); printf("Empty range [5,4]: size=%d\n", size); if (r) free(r); /* Single-element range present */ int a2[] = {7, 8, 9}; r = missingRangeHash(a2, 3, 8, 8, &size); printf("[7,8,9] range [8,8]: "); printArray(r, size); printf("\n"); free(r); /* Single-element range missing */ r = missingRangeHash(a2, 3, 5, 5, &size); printf("[7,8,9] range [5,5]: "); printArray(r, size); printf("\n"); free(r); /* All missing */ int a3[] = {100, 200, 300}; r = missingRangeHash(a3, 3, 1, 4, &size); printf("[100,200,300] range [1,4]: "); printArray(r, size); printf("\n"); free(r); /* None missing */ int a4[] = {1, 2, 3, 4, 5}; r = missingRangeHash(a4, 5, 1, 5, &size); printf("[1..5] range [1,5]: size=%d\n", size); free(r); /* Negative range */ int a5[] = {-3, -1, 0}; r = missingRangeHash(a5, 3, -3, 0, &size); printf("[-3,-1,0] range [-3,0]: "); printArray(r, size); printf("\n"); free(r); /* Large sparse range with hash */ int a6[] = {1000000}; r = missingRangeHash(a6, 1, 999998, 1000002, &size); printf("[1000000] range [999998..1000002]: "); printArray(r, size); printf("\n"); free(r); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); int n = 500000; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return; srand(42); for (int i = 0; i < n; i++) arr[i] = rand() % 1000000; int low = 0, high = 100000; /* r = 100001 */ clock_t start, end; double t; int size = 0; start = clock(); int *r1 = missingRangeNaive(arr, n, low, high, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d, r=%d): size=%d, time=%.3f ms\n", n, high - low + 1, size, t); free(r1); start = clock(); int *r2 = missingRangeSorted(arr, n, low, high, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted (n=%d, r=%d): size=%d, time=%.3f ms\n", n, high - low + 1, size, t); free(r2); start = clock(); int *r3 = missingRangeHash(arr, n, low, high, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d, r=%d): size=%d, time=%.3f ms\n", n, high - low + 1, size, t); free(r3); start = clock(); int *r4 = missingRangeBool(arr, n, low, high, &size); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Boolean (n=%d, r=%d): size=%d, time=%.3f ms\n", n, high - low + 1, size, t); free(r4); free(arr); } 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, low, high; if (readInteger("Enter array size (0-10000): ", &n) != 0 || n < 0 || n > 10000) { printf("Invalid size.\n"); return; } int *arr = NULL; if (n > 0) { arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return; for (int i = 0; i < n; i++) { char p[40]; snprintf(p, sizeof(p), " arr[%d]: ", i); if (readInteger(p, &arr[i]) != 0) { printf("Invalid value.\n"); free(arr); return; } } } if (readInteger("Enter low: ", &low) != 0) { free(arr); return; } if (readInteger("Enter high: ", &high) != 0) { free(arr); return; } int size = 0; int *res = missingRangeHash(arr, n, low, high, &size); printf("Missing: "); printArray(res, size); printf("\n"); free(res); free(arr); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Missing Elements in Range 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: For each candidate in the range, scan the array. Quadratic in r × n.
2. Sorted: Sort once, then advance a pointer while scanning the range.
3. Hash Set: Insert all values, then check each range number in O(1) average.
4. Boolean Array: Mark present indices directly; iterate over r.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: arr=[10,12,11,15], range=[10,15] Array: [10, 12, 11, 15] Naive: [13, 14] Sorted: [13, 14] Hash: [13, 14] Boolean: [13, 14] Verify: PASS Test 2: arr=[1,4,11,51,15], range=[50,55] Array: [1, 4, 11, 51, 15] Naive: [50, 52, 53, 54, 55] Sorted: [50, 52, 53, 54, 55] Hash: [50, 52, 53, 54, 55] Boolean: [50, 52, 53, 54, 55] Verify: PASS === Edge Cases === Empty arr, [1..5]: [1, 2, 3, 4, 5] Empty range [5,4]: size=0 [7,8,9] range [8,8]: [] [7,8,9] range [5,5]: [5] [100,200,300] range [1,4]: [1, 2, 3, 4] [1..5] range [1,5]: size=0 [-3,-1,0] range [-3,0]: [-2] [1000000] range [999998..1000002]: [999998, 999999, 1000001, 1000002]

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Range (low > high)

Return an empty result; never allocate a negative or zero-sized array.

c

if (low > high) { *outSize = 0; return NULL; }

2. Range Size Overflow

high - low + 1 can overflow int.

Solution: Use long long for the range width.

c

long long r = (long long)high - (long long)low + 1;

3. Boolean Array for Very Large Ranges

Allocating r bytes for r = 10⁹ is impractical.

Solution: Use the hash set when r is huge and n is small.

4. Hash Table Sizing

Undersized table causes probe failures.

Solution: Size ≥ 2× n.

5. Negative Values

Cast to unsigned int in the hash function.

6. Duplicate Array Values

Hash insert is idempotent; boolean marking is idempotent. Correct by construction.

7. Mutating Inputs

Sorted approach copies inputs before sorting.

8. Out-of-Range Array Values

The boolean array checks bounds before indexing:

c

if (arr[i] >= low && arr[i] <= high) present[arr[i] - low] = 1;

9. Freeing on Error Paths

Free present and arr copies before returning NULL.

10. Memory Considerations

• Naive: O(r) for result, no extras.
• Sorted: O(n) for the copy.
• Hash: O(n) for the set.
• Boolean: O(r) for the marker array.

---

Summary & Best Practices

Finding missing elements in a range is a clean set-difference problem with multiple efficient solutions. Choose the hash set for sparse large ranges and the boolean array for dense moderate ranges.

Key Takeaways

• Range size r = high - low + 1.
• Naive: O(r × n).
• Sorted: O(n log n + r).
• Hash: O(n + r) average.
• Boolean: O(n + r) with O(r) space.
• Handle low > high as empty.
• Use long long for large ranges.

Best Practices

1. Use the boolean array when r is modest (< 10⁷).
2. Use the hash set when r is huge but n is small.
3. Sort approach when memory is constrained.
4. Guard bounds before indexing in the boolean approach.
5. Cast to unsigned in the hash function for negative keys.
6. Handle low > high without allocating.
7. Use long long for range width when in doubt.
8. Free all dynamic memory.
9. Test edge cases: empty array, empty range, negative range, out-of-range values.
10. Profile for large inputs.

By mastering this problem, you’ll be prepared for gap detection, missing ID resolution, and range-based analytics.