Two-Sum with Hash Lookup

Walk the array once, storing seen values in a lookup structure. In this C source the lookup is a small linear scan over parallel arrays, so the replay shows the complement check before insert.

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^2) for this checked C source because each lookup scans the seen prefix linearly
Space: O(n)

Implementation notes

C stores int arr[] = {2, 7, 11, 4, 5} as a fixed local array and computes n with sizeof(arr) / sizeof(arr[0]) before any pointer decay.
The checked source uses two fixed stack arrays, seen_value[5] and seen_index[5], instead of a library hash table. seen_count marks how many slots are initialized, so there is no empty-slot sentinel.
For each i, need = target - arr[i] is computed first, then the code scans j = 0..seen_count - 1 for a prior value. On a hit it writes first and second and breaks before inserting the current value.
first and second start at -1 as result sentinels. The trace records i=0 as a miss that stores {2: 0}, then i=1 as a hit for need 2 with result [0, 1].
printf("[%d, %d]\n", first, second) formats the two int indices. Visible memory is stack arrays and scalar locals only; visible mutation is appending to the seen arrays and then setting the result indices.

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.