Introduction

Two Sum is one of the most frequently asked coding interview questions at companies like:

• Google
• Amazon
• Microsoft
• Meta
• Apple
• Netflix
• Uber
• Goldman Sachs

Although the problem is simple, interviewers use it to evaluate whether a candidate can:

• Optimize from O(n²) to O(n)
• Choose the correct data structure
• Think about trade-offs
• Write clean production-quality code

Understanding this problem is essential because many advanced problems build on the same HashMap concept.

---

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Assumptions:

• Exactly one solution exists.
• The same element cannot be used twice.
• Return indices, not values.

Example

Input

nums = [2,7,11,15]
target = 9

Output

[0,1]

Explanation

2 + 7 = 9

---

Approach 1 — Brute Force

Idea

Compare every element with every other element.

2

↓

Compare

↓

7

↓

Target Found

---

Java Code

public class TwoSumBruteForce {

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

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

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] + nums[j] == target) {

                    return new int[]{i, j};

                }
            }
        }

        return new int[]{};
    }
}

---

Complexity

Complexity	Value
Time	O(n²)
Space	O(1)

---

Why Brute Force is Bad?

For

100,000 Elements

the number of comparisons becomes enormous.

n²

↓

100000 × 100000

↓

10 Billion Comparisons

Not suitable for production.

---

Approach 2 — HashMap (Optimal)

Core Idea

Instead of searching every element,

store previously visited numbers inside a HashMap.

For every number,

calculate

Complement = Target - CurrentNumber

If the complement already exists,

we found the answer.

---

Algorithm

For each element:

Target = 9

Current = 7

Complement = 2

↓

HashMap contains 2 ?

↓

Yes

↓

Return Indices

---

Dry Run

Array

[2,7,11,15]

Target

9

Step 1

Current

2

Complement

7

HashMap

{}

Store

2 → 0

---

Step 2

Current

7

Complement

2

HashMap

2 → 0

Found!

Return

[0,1]

---

Java Code

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

public class TwoSum {

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

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

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

            int complement = target - nums[i];

            if (map.containsKey(complement)) {

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

            }

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

        }

        return new int[]{};
    }
}

---

Complexity

Complexity	Value
Time	O(n)
Space	O(n)

---

Why HashMap Works?

Instead of searching the array repeatedly,

HashMap provides nearly constant-time lookup.

Array

↓

Current Number

↓

Complement

↓

HashMap Lookup

↓

Found

Average lookup

O(1)

---

Example Walkthrough

Input

nums = [3,2,4]

target = 6

Iteration 1

Current = 3

Need = 3

Map

{}

Store

3 → 0

---

Iteration 2

Current = 2

Need = 4

Map

3 → 0

Store

2 → 1

---

Iteration 3

Current = 4

Need = 2

Map

3 → 0

2 → 1

Answer

[1,2]

---

Edge Cases

Duplicate Values

Input

[3,3]

Target = 6

Output

[0,1]

---

Negative Numbers

[-3,4,3,90]

Target = 0

Output

[0,2]

---

Zero Values

[0,4,3,0]

Target = 0

Output

[0,3]

---

Production Applications

The same HashMap lookup pattern is widely used in enterprise applications.

Examples include:

• Customer lookup by ID
• Session management
• Duplicate request detection
• Fraud detection
• API response caching
• Inventory matching
• Banking transaction reconciliation

HashMap enables fast lookups in all these scenarios.

---

Common Interview Mistakes

❌ Using nested loops after mentioning optimization.

❌ Sorting the array and losing original indices.

❌ Storing values after checking incorrectly.

❌ Returning values instead of indices.

❌ Ignoring duplicate numbers.

---

Follow-Up Questions

What if the array is sorted?

Use the Two Pointer technique.

Time Complexity

O(n)

Space Complexity

O(1)

---

What if multiple answers exist?

Return:

• First pair
• All pairs
• Count of pairs

depending on the problem statement.

---

What if the array is extremely large?

Possible optimizations:

• Parallel processing
• Distributed computation
• External memory algorithms
• Streaming approaches

---

Interview Tips

Interviewers often ask:

• Why HashMap?
• Why not sorting?
• Why O(n)?
• What happens with duplicates?
• Can you reduce memory usage?
• What if the array is sorted?
• What if there are multiple solutions?
• Explain the dry run.
• Explain time and space complexity.
• Can this be solved without extra space?

Be prepared to explain the intuition before writing code.

---

Summary

Two Sum is the foundation of many HashMap-based interview problems. The brute-force approach is easy to understand but inefficient with O(n²) time complexity. Using a HashMap reduces the lookup time to O(1) on average, resulting in an overall O(n) solution. Mastering this problem builds a strong foundation for solving more advanced array and hashing questions.

---

Key Takeaways

• Understand the problem before coding.
• Start with the brute-force solution.
• Optimize using a HashMap.
• Calculate the complement efficiently.
• Store visited elements.
• Achieve O(n) time complexity.
• Handle duplicates and edge cases.
• Explain the trade-offs clearly.
• Relate the solution to real-world systems.
• Practice dry runs to improve interview confidence.

---