1. Understanding the Problem

The premise is straightforward. You are given an array (or list) of numbers and a specific target number. Your job is to find the two numbers in that array that add up perfectly to the target, and then return their index positions.

The Rules:

• There is exactly one valid solution in the array.
• You cannot use the exact same element (the same index) twice.
• The order of the indices you return does not matter.

A Quick Example

Imagine your array is [2, 7, 11, 15] and your target is 9.

You look at the numbers. You see that 2 + 7 = 9. Because the number 2 is at index 0, and the number 7 is at index 1, your answer is simply [0, 1].

2. The Brute Force Approach (The Intuitive Starting Point)

When faced with this problem, the most natural human instinct is to check every single combination.

You start at the first number. Then, you look at every other number in the list to see if they add up to the target. If they don't, you move to the second number and check all remaining numbers, and so on.

Trade-off Analysis

While this method guarantees you will find the answer, it is incredibly slow for large datasets. In system design and algorithm analysis, we evaluate this using Big O notation:

• Time Complexity: O(N²) — Because for every number, you are looping through the rest of the array. As the array grows, the time it takes grows exponentially.
• Space Complexity: O(1) — You aren't storing any extra data, making it very memory efficient.

3. The Optimal Approach: The Hash Map (The "Aha!" Moment)

To pass a senior-level technical interview, we need to optimize our time complexity. We want to traverse the array only once, dropping our time complexity to O(N). To do this, we must make a trade-off: we will sacrifice a little bit of memory to gain a massive amount of speed.

Instead of thinking: "What number can I add to my current number to reach the target?"

We reframe the math: "Target - Current Number = The Missing Piece"

The Logic Step-by-Step

1. We create an empty Hash Map (a Dictionary in Python). This will store the numbers we have already looked at, and their index positions.
2. We loop through the array exactly one time.
3. For each number, we calculate its Missing Piece (Target - Current Number).
4. We check our Hash Map: Have we already seen this Missing Piece earlier in the array?
   • If YES: We found our pair! We return the index of the Missing Piece (from the map) and our current index.
   • If NO: We store our current number and its index in the Hash Map so that future numbers can look back and find it.

4. Code Implementations

Now that you understand the mechanics, view the optimal O(N) implementation in your preferred language below.

def twoSum(nums, target):
    # This dictionary will map values to their indices
    seen = {}
    
    for current_index, current_number in enumerate(nums):
        missing_piece = target - current_number
        
        # If the missing piece is in our map, we found the pair!
        if missing_piece in seen:
            return [seen[missing_piece], current_index]
            
        # Otherwise, add the current number and its index to the map
        seen[current_number] = current_index
        
    return []

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Map to store the numbers we've seen and their indices
        Map<Integer, Integer> seen = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int missingPiece = target - nums[i];
            
            // Check if we've seen the missing piece
            if (seen.containsKey(missingPiece)) {
                return new int[] { seen.get(missingPiece), i };
            }
            
            // Store the current number and index
            seen.put(nums[i], i);
        }
        
        return new int[] {};
    }
}

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> seen;
        
        for (int i = 0; i < nums.size(); i++) {
            int missingPiece = target - nums[i];
            
            if (seen.count(missingPiece)) {
                return {seen[missingPiece], i};
            }
            
            seen[nums[i]] = i;
        }
        
        return {};
    }
};

5. Conclusion: You Are Ready

You now know how to solve Two Sum. More importantly, you know why the Hash Map solution is optimal. You understand how trading memory space for execution time transforms a slow, O(N²) algorithm into a lightning-fast O(N) solution. Take a breath, write out the logic on a piece of paper, and you will see just how capable you are of mastering this concept.