Array & Data-Structure Operations
Two Sum
Finds two indexes whose values add up to a target in one pass, storing each value's index in a hash map and looking up the complement (target − value).
1Detailed explanation
Two Sum asks for two indexes whose values add up to a target. The brute force checks every pair in O(n²).
The one-pass hash-map solution walks the array once. For each value it computes complement = target − value and asks the map whether that complement was seen earlier. If yes, the pair is found; if not, it stores value → index and moves on.
This trades O(n) extra memory for O(n) time — the most common optimisation pattern in interviews.
2Pseudocode
procedure twoSum(nums, target)
seen ← empty hash map // value → index
for i ← 0 to length(nums) − 1
complement ← target − nums[i]
if complement ∈ seen
return [seen[complement], i]
seen[nums[i]] ← i
return []3Interactive visualization
Finds two indexes whose values add up to a target in one pass, storing each value's index in a hash map and looking up the complement (target − value).
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(nums[i], i);
}
return [];
}
const nums = [3, 8, 11, 2, 7, 15];
const target = 9;
console.log("Indices:", twoSum(nums, target));
5Time and space complexity
Time: Each element is visited once and every hash-map lookup/insert is O(1) on average, so the scan is O(n). (The brute-force approach checks every pair → O(n²).) Hash maps can degrade to O(n) per operation with many collisions, but that is rare in practice.
Space: In the worst case (pair found at the very end, or no pair) the map stores n−1 entries → O(n) auxiliary space. This is the classic time/space trade-off versus the O(1)-space brute force.
6Common interview variations
- Two Sum II on a sorted array with two pointers in O(1) space.
- Return all unique pairs (handle duplicates).
- 3Sum and 4Sum.
- Two Sum in a BST.
- Count pairs with a given difference.