Two Sum
Understand the problem
You're given an array nums and an integer target. Find two indices i, j (i ≠ j) such that nums[i] + nums[j] === target, and return that pair of indices.
Example:
nums = [2, 7, 11, 15], target = 9
output = [0, 1] // because nums[0] + nums[1] = 2 + 7 = 9Assumption: there is always exactly one solution.
You can't use the same element twice.
Show the basic approach (slower)
O(n²) time, O(1) spacefunction twoSum(nums: number[], target: number): [number, number] | null {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j]
}
}
return null
}Two nested loops check every pair of elements.
With n=10⁴ that is 10⁸ comparisons, which exceeds the time limit.
Optimal solution
O(n) time, O(n) spacefunction twoSum(nums: number[], target: number): [number, number] | null {
const seen = new Map<number, number>() // value → index
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 null
}Use a hash map to store each value you have seen along with its index.
- At each step you only need to look up
target - nums[i]to see whether it is already there — O(1) on average. - Trade-off: O(n) extra space to bring the time down from O(n²) to O(n).
Step-by-step trace
1function twoSum(nums: number[], target: number): [number, number] | null {2 const seen = new Map<number, number>() // value → index3 for (let i = 0; i < nums.length; i++) {4 const complement = target - nums[i]5 if (seen.has(complement)) return [seen.get(complement)!, i]6 seen.set(nums[i], i)7 }8 return null9}Edge cases to remember
Two equal elements that sum to target (e.g. [3, 3], target=6) — still correct, because we check
seenBEFORE storing, so index 0 and index 1 never collide.Negative numbers: target=-5, nums=[-3, -2] → complement=-5-(-3)=-2, found correctly.
Zero: nums=[0, 4, 3, 0], target=0 → returns [0, 3], never the same index twice.
Empty array or a single element — the problem assumes a solution always exists, but the code still returns null when nothing is found, to avoid crashing.