The Two Sum problem is a classic coding interview question. Given an array of integers and a target sum, we need to find two numbers in the array that add up to the target and return their indices. For example, with array [2, 7, 11, 15] and target 9, the answer is indices [0, 1] because 2 plus 7 equals 9.
The brute force approach uses two nested loops to check every possible pair of numbers. We use pointer i for the first number and pointer j for the second number, starting from i plus 1. This ensures we don't use the same element twice and avoid duplicate pairs. The time complexity is O(n squared) because we check all pairs, and space complexity is O(1) as we only use constant extra space.
The hash map approach is much more efficient. As we iterate through the array, we calculate the complement needed to reach the target. We check if this complement already exists in our hash map. If it does, we found our answer. If not, we store the current number and its index in the hash map for future lookups. This reduces time complexity to O(n) with O(n) space complexity.
Let's walk through the algorithm step by step with our example. We have array [2, 7, 11, 15] and target 9. Step 1: We check number 2 at index 0. The complement is 9 minus 2 equals 7. Since 7 is not in our hash map yet, we add 2 with index 0 to the map. Step 2: We check number 7 at index 1. The complement is 9 minus 7 equals 2. We find 2 in our hash map at index 0, so we return [0, 1] as our answer.
To summarize, the Two Sum problem is best solved using a hash map approach. This gives us optimal O(n) time complexity with O(n) space complexity. The key insight is to store each number and its index as we iterate, allowing us to find complements in constant time. This solution is efficient, elegant, and commonly asked in coding interviews. Remember to handle edge cases and always consider the trade-off between time and space complexity when solving algorithmic problems.