Introduction

While the Two Sum problem itself is straightforward, it is highly popular because it perfectly demonstrates how a simple change in data structures can optimize an algorithm from painfully slow to lightning fast.

In this guide, we will break down the problem statement, explore a naive solution, and then unlock the highly efficient, optimized approach using a hash map—all in simple, everyday language.

---

Understanding the Problem

The problem asks us to find two numbers in an array that add up to a specific target number. Once we find those two numbers, we need to return their indices (their positions in the array).

Rules to Remember

• Each input has exactly one solution.
• You cannot use the same element twice to make the sum.
• You can return the answer in any order.

A Quick Example

Imagine you are given this array of numbers and a target:

• Numbers (nums): [2, 7, 11, 15]
• Target: 9

If we look at the array, nums[0] (which is 2) and nums[1] (which is 7) add up to 9. Therefore, our output should be their indices: [0, 1].

---

Approach 1: The Brute Force (The "Check Everything" Way)

The most intuitive way to solve this is to behave like a human looking for a lost item: check every single possible combination until you find the right one.

We can use two loops (nested loops). The outer loop picks a number, and the inner loop checks all the subsequent numbers to see if they add up to the target.

java
Copy
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Loop through every number
        for (int i = 0; i < nums.length; i++) {
            // Loop through the numbers that come after 'i'
            for (int j = i + 1; j < nums.length; j++) {
                // If they add up to the target, we found our pair!
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        // In case no solution is found
        return new int[] {};
    }
}

Why it's not optimal

• Time Complexity: O(N²) — where N is the number of elements. If your array has 10,000 numbers, this code might check nearly 100 million pairs!
• Space Complexity: O(1) — it uses virtually no extra memory, which is its only perk.

---

Approach 2: The Optimized Way (The "Memory Match" Way)

Can we do better? Yes! We can trade a little bit of memory space to gain a massive boost in speed.

Instead of checking every pair, we can use a Hash Map (or dictionary). A Hash Map allows us to look up information almost instantly.

The Core Concept

Instead of searching for two numbers that add up to target, we can rephrase the question. If we are currently looking at a number x, we know exactly what its matching partner has to be:

Complement = Target - x

As we walk through the array, we check our Hash Map to see if we have already encountered this required complement. If we have, we instantly win! If we haven't, we store our current number and its index in the map and move to the next item.

Let's trace it step-by-step:

Given nums = [2, 7, 11, 15] and target = 9:

1. Index 0 (Number = 2):

   • Complement = 9 - 2 = 7
   • Is 7 in our map? No, our map is empty.
   • We add 2 (index 0) to our map. Map state: {2: 0}.

2. Index 1 (Number = 7):

   • Complement = 9 - 7 = 2
   • Is 2 in our map? Yes! It’s at index 0.
   • We immediately return [0, 1].

We solved it in a single pass through the array!

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Create a hash map to store numbers and their indices
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // Check if the required complement is already in our map
            if (map.containsKey(complement)) {
                // Return the index of the complement and the current index
                return new int[] { map.get(complement), i };
            }
            
            // If not found, save the current number and index for future numbers
            map.put(nums[i], i);
        }
        
        return new int[] {};
    }
}

Why this is brilliant

• Time Complexity: O(N) — we only loop through the array exactly once. Looking up items inside a HashMap takes O(1) constant time on average.
• Space Complexity: O(N) — in the worst-case scenario, we might have to store all the elements of the array inside our map before finding a match.

---

Final Thoughts

The evolution of the solution to the Two Sum problem highlights one of the most core philosophies in Computer Science: Trading space for time.

By utilizing a small amount of extra memory (the Hash Map), we transformed a sluggish algorithm that slows down drastically with large datasets into a linear execution masterpiece that finishes almost instantly.