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.cpp

#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<int> arr{2, 7, 11, 4, 5};
    int target = 9;
    std::unordered_map<int, int> seen;
    int first = -1;
    int second = -1;
    for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
        int need = target - arr[i];
        auto it = seen.find(need);
        if (it != seen.end()) {
            first = it->second;
            second = i;
            break;
        }
        seen[arr[i]] = i;
    }
    std::cout << "[" << first << ", " << second << "]\n";
    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.