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

execution replay The checked-in replay follows the language-neutral state table for `array-two-sum-hash`.
cross-language comparison This Fortran DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.f90
Replay: real traced execution (multi-file project)
program array_two_sum_hash
    implicit none
    integer :: arr(5) = [2, 7, 11, 4, 5]
    integer :: seen_value(5), seen_index(5)
    integer :: target, seen_count, first, second, i, j, need
    logical :: found
    target = 9
    seen_count = 0
    first = -1
    second = -1
    found = .false.
    do i = 1, 5
        need = target - arr(i)
        do j = 1, seen_count
            if (seen_value(j) == need) then
                first = seen_index(j)
                second = i - 1
                found = .true.
                exit
            end if
        end do
        if (found) exit
        seen_count = seen_count + 1
        seen_value(seen_count) = arr(i)
        seen_index(seen_count) = i - 1
    end do
    print '("[", I0, ", ", I0, "]")', first, second
end program array_two_sum_hash

  1. arr ← [2, 7, 11, 4, 5], target ← 9, seen ← {}

    1program array_two_sum_hash2    implicit none
    values this step[2, 7, 11, 4, 5]arr9target{}seen

  2. seen ← {2: 0}, hit ← no

    4integer :: seen_value(5), seen_index(5)5integer :: target, seen_count, first, second, i, j, need6logical :: found
    values this step{} → {2: 0}seennohit0i2arr[i]7need

  3. hit ← yes, result ← [0, 1]

    4integer :: seen_value(5), seen_index(5)5integer :: target, seen_count, first, second, i, j, need6logical :: found
    values this stepyeshit[0, 1]result1i7arr[i]2need{2: 0}seen

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.