Two Sum
Store what you've seen so each element only looks up its complement.
Approach
The brute force checks every pair in O(n²). Instead, walk the array once and keep a hash map of value → index. For each number, check whether its complement (target − num) is already in the map; if so you're done, otherwise record the current number. You trade O(n) memory for a single linear pass.
Time complexity
O(n)
Space complexity
O(n)
Common mistake
Adding a number to the map before checking for its complement — that can match an element with itself. Check first, then insert.
See it run, step by step
Generate an interactive lesson for Two Sum — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Two Sum