Easy Hashing
Two Sum
Receives an array of integers and a target value, and returns the indices of the two numbers that add up to the target. It scans the array once, keeping a hash map from each value seen so far to its index: at each element it computes the complement (target minus the current value) and checks whether that complement is already a key in the map — if so, the pair is found immediately; otherwise the current value is recorded in the map and the scan continues. This trades a little extra memory for speed, running in O(n) instead of the O(n²) of checking every pair. Returns a new array with the two matching indices in the order [earlier, later]; returns an empty array when no such pair exists.
Visualization
- Input
- Result
Algorithm code
// Two Sum — a single pure function. Receives an array of integers and a
// target value, and returns the indices of the two numbers that add up to
// the target, using a hash map (value -> index) to find the complement of
// each number in a single pass, in O(n).
/**
* @param {number[]} arr - array of integers
* @param {number} target - the target sum
* @returns {number[]} the two indices whose values add up to target, or [] if no such pair exists
*/
export function twoSum(arr, target) {
const seen = new Map();
for (let i = 0; i < arr.length; i += 1) {
const complement = target - arr[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(arr[i], i);
}
return [];
}FUNCTION twoSum(arr, target):
seen ← empty map
FOR i ← 0 TO length(arr) - 1:
complement ← target - arr[i]
IF seen HAS complement:
RETURN [seen[complement], i]
seen[arr[i]] ← i
RETURN []