How a Hash Map Cuts the Classic Two Sum Problem from O(n²) to O(n)

The Two Sum problem asks developers to find indices of two numbers in an array that add up to a given target. A naive brute-force approach uses nested loops, resulting in O(n²) time complexity that slows significantly as input size grows. The key insight is to use a hash map to store previously seen values, allowing each element's required complement to be looked up in constant time. This reduces the solution to a single pass through the array, achieving O(n) time at the cost of O(n) extra space. A common mistake is storing the complement rather than the actual value seen, which can cause incorrect lookups; the correct approach records each number and its index before checking for its partner.