Algorithms and Data Structures · Junior · Question 62 of 75
Two Sum: find two numbers in an unsorted array that add up to target. What is the O(n) approach?
- 1Sort the array and return its two smallest elements
- 2Try every possible pair with two nested loops
- ✓Correct answer: Check whether
target - xis in a map of numbers seen so far
Explanation
One pass: if target - x was seen before, the pair is found; otherwise remember x and its index. Trying every pair is O(n²). Sorting gives O(n log n) and loses the original indices.