The Two Sum Problem

You and your best friend walk into a shiny gadget store. Together, you have ₹1000 in your pocket, and your mission is simple:

Buy two items that together cost exactly ₹1000.

But here’s the twist: the store has a ton of gadgets, and their prices are scattered all over the place.

The prices are: [350, 600, 150, 450, 550]

You pick up a ₹450 gadget and start calculating in your head:

If I buy this one… I need something that costs ₹550 to make the total ₹1000."

Your friend scans the shelves and, boom! 💥 Finds the ₹550 item.

You both grab them and head to the checkout.

That is the Two Sum problem in action. But instead of gadgets, we’re working with numbers in an array. Let’s take a closer look at the problem.

🎯 What’s the Two Sum Problem?

At its core, the Two Sum problem is simple:

• You are given an array of numbers (like prices, but could be anything).
• You also have a target number, which is like your budget.
• Your goal is to find two numbers in the array that add up to the target and return their positions (indices).

📦 Example

Imagine we have the following input:

Input: nums = [2, 7, 11, 15]

Target: 9

Output: [0, 1]

Why?

Because nums[0] + nums[1] = 2 + 7 = 9

So, the answer is the indices [0, 1].

🧠 How Does the Code Think?

Now, how does the code solve this? Let’s break it down step-by-step:

The idea is to remember the numbers you’ve already seen and ask yourself:

"What number do I need to reach the target?"

Here’s how the code thinks:

Step-by-Step Breakdown

1. Start with an empty map (like your shopping list). This will store the numbers you've seen and their positions.

2. Loop through each number in the array.

3. For each number, calculate the complement — the number you need to reach the target.

4. Check if this complement is already in your map:

• If yes, it means you’ve found the pair! Return the positions (indices).
• If no, add the current number to the map and move on.

This is the secret sauce:

“What number do I need to finish the sum?”

→ “Have I seen that number before?”

→ “If yes, return both indices.”

→ “If no, save the number I have and keep going.”

🔧 The Code

Let’s translate that thinking into code:

class Solution

{

public int[] twoSum(int[] nums, int target)

{

// Your memory notebook (HashMap)

HashMap<Integer, Integer> map = new HashMap<>();

// Loop through the array of numbers

for (int i = 0; i < nums.length; i++)

{

// Calculate the complement number we need to finish the target

int complement = target - nums[i];

// Have we seen this complement before?

if (map.containsKey(complement))

{

// Yes! Return the indices

return new int[] { map.get(complement), i };

}

// If not, add the current number and its index to the map

map.put(nums[i], i);

}

// If no valid pair is found, return [-1, -1]

return new int[] { -1, -1 };

}

}

🔍 Let’s Walk Through It — Like We’re Shopping!

Let’s take the example:

nums = [2, 7, 11, 15]

target = 9

Start with an empty shopping list (map): {}

1. i = 0 → nums[0] = 2

- Needed: 9 - 2 = 7

- Map: 7 not found → add 2 to map: {2: 0}

2. i = 1 → nums[1] = 7

- Needed: 9 - 7 = 2

- Map: YES! 2 is already in the map → return [0, 1] 🎯

Why Not Just Try Every Pair?

You might be thinking, "Why not just use two loops and check every possible pair?" Well, that's the brute-force way, and it’s slow. Imagine checking every possible pair in a store, one by one. That's time-consuming and inefficient.

Instead, using a HashMap makes it faster. By remembering the numbers you've already seen, you can quickly check if the number you need is available, without looping through everything again.

This approach works in O(n) time, which is way faster than checking every pair.

The Key Takeaways

1. You have a target (your budget).

2. Loop through the array.

3. For each number:

- Calculate the complement (what number do I need to make the sum?).

- If you’ve seen it before, return the pair.

- If not, save this number for later.

4. Done!