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

  • In C++, the input is a std::vector<int> initialized as {2, 7, 11, 4, 5} and the lookup table is std::unordered_map<int, int>, mapping a seen value to its earlier index.
  • The loop index is an int and compares against static_cast<int>(arr.size()); each arr[i] read stays inside the vector bounds used by the trace.
  • int need = target - arr[i] computes the complement, and seen.find(need) checks without inserting a missing key. Only seen[arr[i]] = i mutates the hash table after a miss.
  • The trace records {} at start, then a miss for need 7 and insert {2: 0}, then a hit for need 2 at i=1, producing result [0, 1].
  • first and second are scalar int result slots initialized to -1; the source prints them with std::cout << "[" << first << ", " << second << "]\n".
  • Visible allocation is the vector storage and unordered-map buckets/nodes. The source does not reserve buckets or expose collision behavior in the replay, so the trace shows logical lookup state rather than bucket layout.
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.