Arrays and Iteration
Two-Sum with Hash Lookup
Walk the array once, storing seen values in a lookup table. When the complement is already present, the result indices are known.
Algorithm
Basic Implementation
basic.c
#include <stdio.h>
int main(void) {
int arr[] = {2, 7, 11, 4, 5};
int n = (int)(sizeof(arr) / sizeof(arr[0]));
int target = 9;
int seen_value[5];
int seen_index[5];
int seen_count = 0;
int first = -1;
int second = -1;
for (int i = 0; i < n; ++i) {
int need = target - arr[i];
for (int j = 0; j < seen_count; ++j) {
if (seen_value[j] == need) {
first = seen_index[j];
second = i;
break;
}
}
if (first != -1) {
break;
}
seen_value[seen_count] = arr[i];
seen_index[seen_count] = i;
seen_count++;
}
printf("[%d, %d]\n", first, second);
return 0;
}
Complexity
- Time: O(n) average
- Space: O(n)
Implementation notes
- Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
- The final output is intentionally small and deterministic for cross-language comparison.
execution replay
The checked-in replay follows the language-neutral state table for `array-two-sum-hash`.
cross-language comparison
This C DSA version keeps the same data and final output as every other DSA book in this wave.