Mastering Two Sum: The Gateway to Coding Interviews in Python

If there is one problem that perfectly represents the beginning of a coding interview journey, it is Two Sum. This problem appears in interviews at almost every level—not because it is hard, but because it teaches how engineers think about optimization.

Two Sum introduces you to:

• Translating a mathematical idea into code
• Identifying inefficiencies in a naïve solution
• Making deliberate time vs. space trade-offs
• Using a hash map, one of the most powerful interview tools

By mastering Two Sum, you are not just solving one problem—you are learning a pattern that applies to dozens of interview questions.

The Problem Statement

You are given:

• An array of integers nums
• An integer target

Your task is to return the indices of the two numbers such that they add up to the target.

Constraints

• Each input has exactly one solution
• You may not use the same element twice
• The order of indices does not matter

Example

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

Output

[0, 1]

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

Approach 1: The Brute Force

Logic

The brute-force approach checks every possible pair:

• Pick one number
• Compare it with every number after it
• Return the indices when the sum matches the target

This approach is intuitive and often the first solution beginners think of.

Python Code

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]

Why This Is Inefficient

This solution works, but it scales poorly.

• Time Complexity: Nested loops → O(n²) As the input grows, the number of comparisons explodes.

• Space Complexity: No extra memory used → O(1)

In interviews, this solution is usually accepted as a baseline, but you are expected to improve it.

Understanding the Key Optimization Idea

To optimize Two Sum, we need to rethink the problem.

The equation:

nums[i] + nums[j] = target

Can be rewritten as:

nums[j] = target - nums[i]

The value target - nums[i] is called the complement.

Why Do We Check the Complement?

For every number, there is only one number that can complete it to reach the target.

Instead of asking:

“Do any two numbers add up to the target?”

We ask:

“Have I already seen the number that completes the current one?”

This insight removes the need for nested loops.

Approach 2: The Optimized Hash Map Solution

What Is a Hash Map?

A hash map stores key–value pairs and allows fast lookup.

In Python, a hash map is called a dictionary.

seen = {}

Why Python Can “Jump Straight” to Values

Python dictionaries use a hash table internally:

• A hash function converts the key into a number
• That number maps directly to a memory location
• Python retrieves the value without searching

This is why dictionary lookups are O(1) on average.

Optimized Logic

As we loop through the array:

1. Compute the complement: target - current_value
2. Check if the complement already exists in the dictionary
3. If it does, we’ve found the solution
4. Otherwise, store the current value and its index

We check before storing to avoid using the same element twice.

Python Code

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

Why This Solution Is Faster

• We loop through the array once
• Each dictionary lookup is O(1)
• No repeated comparisons

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) (extra memory for the hash map)

This is the solution interviewers expect you to arrive at.

Time and Space Complexity Explained Simply

• Time Complexity describes how runtime grows as input grows
• Space Complexity describes how much extra memory is used

Two Sum Comparison

This is a classic example of trading space for speed.

Key Takeaways

• Two Sum teaches problem-solving patterns, not just syntax
• Always start simple, then optimize
• Checking the complement turns pairing into a lookup problem
• Hash maps enable constant-time access and are interview essentials

Final Interview Insight

If you can:

• Explain the brute-force approach
• Identify its inefficiency
• Introduce the complement idea
• Justify the hash map trade-off

You’re not just solving Two Sum—you’re demonstrating engineering thinking, which is exactly what interviews are designed to test.