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 Rust DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.rs
Replay: real traced execution (multi-file project)
fn main() {
	let arr = [2, 7, 11, 4, 5];
	let target = 9;
	let mut seen = std::collections::HashMap::new();
	let mut result = (-1, -1);
	for (i, value) in arr.iter().enumerate() {
		let need = target - value;
		if let Some(j) = seen.get(&need) {
			result = (*j as i32, i as i32);
			break;
		}
		seen.insert(*value, i);
	}
	println!("[{}, {}]", result.0, result.1);
}

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

    1fn main() {2	let arr = [2, 7, 11, 4, 5];
    values this step[2, 7, 11, 4, 5]arr9target{}seen

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

    6for (i, value) in arr.iter().enumerate() {7	let need = target - value;8	if let Some(j) = seen.get(&need) {
    values this step{} → {2: 0}seennohit0i2arr[i]7need

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

    6for (i, value) in arr.iter().enumerate() {7	let need = target - value;8	if let Some(j) = seen.get(&need) {
    values this stepyeshit[0, 1]result1i7arr[i]2need{2: 0}seen

Complexity

  • Time: O(n) average
  • Space: O(n)

Implementation notes

  • The checked source uses a fixed array literal, let arr = [2, 7, 11, 4, 5], not a Vec.
  • let mut seen = std::collections::HashMap::new() builds a mutable map from copied i32 values to usize indices.
  • The loop uses arr.iter().enumerate(), so i is a usize and value is a borrowed &i32. Arithmetic target - value relies on Rust's integer subtraction over the referenced scalar.
  • Lookup happens before insertion: seen.get(&need) returns Option<&usize>. On Some(j), the code copies *j, casts both indices to i32, stores result = (*j as i32, i as i32), and breaks.
  • On a miss, seen.insert(*value, i) copies the current value into the map. No duplicate update is reached in this trace.
  • The trace records seen={} at start, then i=0 with need=7 as a miss and seen={2: 0}. At i=1, need=2 hits and records result [0, 1].
  • println!("[{}, {}]", result.0, result.1) prints the deterministic index pair [0, 1]; the code never iterates over seen, so hash-map iteration order is irrelevant.