LeetCode : Two Sum — The First Problem Every Programmer Should Master

LeetCode Problem: Two Sum
Difficulty: Easy
Topics: Array, Hash Table
Series: LeetCode Interview Preparation — From Beginner to Expert

If you are preparing for a software engineering interview, there is a good chance you will encounter a problem similar to Two Sum.

It looks extremely simple:

Given an array of integers and a target value, find two numbers whose sum equals the target.

But Two Sum teaches one of the most important skills in coding interviews:

How to take a brute-force solution and optimize it using the right data structure.

This makes it the perfect starting point for our Kairos Coders LeetCode Interview Preparation Series.

The Problem

You are given an integer array nums and an integer target.

Find the indices of two numbers such that:

nums[i] + nums[j] = target

You may assume that:

• There is exactly one valid answer.
• You cannot use the same element twice.
• The answer can be returned in any order.

Example

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

Output:
[0, 1]

Why?

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

Therefore, the answer is:

[0, 1]

First Thought: Brute Force

The most obvious solution is to check every possible pair.

For every element:

1. Pick the first number.
2. Pick another number.
3. Check whether their sum equals the target.

For:

[2, 7, 11, 15]

we would check:

2 + 7  = 9  ✓
2 + 11 = 13
2 + 15 = 17
7 + 11 = 18
7 + 15 = 22
11 + 15 = 26

We eventually find the answer.

Brute-Force Code

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

    return []

This solution is correct.

But can we do better?

Absolutely.

Why Is Brute Force Slow?

The problem is the nested loop.

For every element, we potentially check every other element.

If the array contains n elements, the number of comparisons can approach:

n × n

Therefore:

Time Complexity

O(n²)

Space Complexity

O(1)

For a small array, this is fine.

But imagine:

n = 100,000

Checking potentially billions of combinations is clearly inefficient.

This is where interviewers expect you to think about data structures.

The Key Observation

Suppose we are currently looking at:

nums[i] = 2

and:

target = 9

What number do we need?

Simple:

9 - 2 = 7

So instead of asking:

"Which other numbers should I try?"

we can ask:

"Have I already seen the number I need?"

This changes the entire problem.

Introducing the Hash Map

A hash map allows us to store values and quickly check whether a value already exists.

In Python, we can use a dictionary.

We'll store:

number → index

For example:

{
    2: 0,
    7: 1
}

Now we can check whether a required number exists in approximately constant time.

Optimized Approach

Let's walk through the example:

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

Initially:

seen = {}

Step 1

Current number:

2

Calculate the number we need:

9 - 2 = 7

Is 7 already in the map?

No

Store:

seen = {
    2: 0
}

Step 2

Current number:

7

Calculate:

9 - 7 = 2

Is 2 already in the map?

Yes!

We stored:

2 → index 0

The current index is:

1

Therefore:

[0, 1]

is our answer.

Optimized Python Solution

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

    return []

This is the solution you should understand rather than simply memorize.

Understanding the Code

Let's break it down.

Create the Hash Map

seen = {}

This stores numbers we have already encountered.

Iterate Through the Array

for i, num in enumerate(nums):

For every element, we have:

i    → index
num  → current value

For example:

i = 0
num = 2

Find the Complement

complement = target - num

If:

target = 9
num = 2

then:

complement = 9 - 2
complement = 7

So we need 7.

Check the Hash Map

if complement in seen:

We ask:

Have we already encountered the number we need?

If yes, we have found our pair.

Return the Indices

return [seen[complement], i]

The dictionary contains the index of the previous number.

Store the Current Number

If the complement isn't found:

seen[num] = i

We save the current number for future iterations.

Dry Run

Let's make the process visual.

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

The algorithm stops immediately after finding the answer.

Why Does This Work?

The fundamental equation is:

a + b = target

Rearrange it:

b = target - a

Therefore, for every number a, we only need to check whether:

target - a

has already appeared.

The hash map makes that lookup extremely fast.

This is the central idea behind the solution.

Complexity Analysis

We iterate through the array once.

For each element, we perform hash-map operations that are O(1) on average.

Therefore:

Time Complexity

O(n)

Space Complexity

O(n)

We potentially store every element in the hash map.

O(n²) vs O(n)

This is the important interview lesson.

We traded some memory for a significant improvement in execution time.

This is one of the most common optimization techniques in programming interviews.

Common Mistake #1: Using the Same Element Twice

Consider:

nums = [3]
target = 6

You cannot use the same 3 twice.

That's why our algorithm checks the complement before storing the current number:

if complement in seen:
    return [seen[complement], i]

seen[num] = i

This ordering matters.

Common Mistake #2: Returning Values Instead of Indices

The problem asks for:

[0, 1]

not:

[2, 7]

Always carefully read what the problem asks you to return.

Common Mistake #3: Sorting the Array Without Thinking

You might think:

"I can sort the array and use two pointers."

That's a valid strategy for a variation of the problem, but there is an important problem here.

The question asks for original indices.

If you sort the array, you change the positions.

You would therefore need additional bookkeeping to preserve the original indices.

The hash-map solution avoids this complication.

Interviewer's Follow-Up Questions

Once you solve Two Sum, an interviewer might ask:

1. Can you solve it without extra space?

Yes, a brute-force approach uses O(1) extra space but takes O(n²) time.

If the interviewer insists on O(1) auxiliary space while preserving the original array, the trade-off becomes more complicated because you need to maintain index information.

2. What if the array is sorted?

If the input is already sorted, a two-pointer approach becomes possible.

Example:

[2, 7, 11, 15]

Use:

left  → beginning
right → end

Then:

• If sum is too small → move left
• If sum is too large → move right
• If sum equals target → answer found

This gives:

O(n)

time and:

O(1)

extra space.

3. What if there are multiple valid pairs?

Then the problem definition matters.

You might need to:

• Return any valid pair
• Return all pairs
• Return unique pairs
• Count the number of pairs

Each variation may require a different implementation.

The Bigger Pattern: Complement Lookup

This problem isn't really about Two Sum.

It teaches a reusable pattern:

Current Value
      ↓
What do I need?
      ↓
Target - Current Value
      ↓
Have I seen it before?
      ↓
Hash Map Lookup

You will see this idea repeatedly in interview questions involving:

• Pair sums
• Frequency counting
• Duplicate detection
• Subarray problems
• String matching
• Counting occurrences
• Complement relationships

Once you recognize this pattern, many problems become much easier.

How to Recognize This Pattern in an Interview

When you see a problem containing something like:

"Find two elements..."

or:

"Find whether two values add up to..."

or:

"Find a pair satisfying..."

Immediately ask yourself:

Can I calculate what the missing value must be?

For Two Sum:

missing = target - current

Then ask:

Can a hash map help me remember what I've already seen?

This thought process is more valuable than memorizing the code.

Alternative Solution: Two Pointers

If the array is sorted, we can solve the problem using two pointers.

def twoSumSorted(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return [left, right]

        if total < target:
            left += 1
        else:
            right -= 1

    return []

The idea:

        ↓           ↓
[2, 7, 11, 15]
 L               R

If:

2 + 15 = 17

which is greater than:

9

we move the right pointer:

2 + 11 = 13

Still too large.

Move again:

2 + 7 = 9

Found it.

What You Should Learn From This Problem

Don't just remember:

seen = {}

Remember the reasoning:

Step 1

Start with the obvious brute-force solution.

Step 2

Identify why it is slow.

Step 3

Look for repeated work.

Step 4

Ask whether a data structure can make that work faster.

Step 5

Use a hash map to remember previous values.

Step 6

Convert:

a + b = target

into:

b = target - a

Step 7

Look up the complement in O(1) average time.

This is problem-solving, not memorization.

Interview Cheat Sheet

Before your interview, remember:

Problem:
Find two numbers whose sum equals target.

Brute Force:
Try every pair.

Brute Force:
O(n²) time
O(1) space

Optimized:
Hash Map

For every number:
complement = target - number

If complement exists:
return its index + current index

Otherwise:
store current number.

Optimized:
O(n) average time
O(n) space

Practice Challenge

Now try solving these variations yourself:

Challenge 1

Find whether any pair adds up to a target.

Challenge 2

Return the number of pairs that add up to a target.

Challenge 3

Find all unique pairs whose sum equals the target.

Challenge 4

Solve Two Sum when the input array is already sorted.

Challenge 5

Solve the problem using two pointers.

These variations will help you understand the underlying pattern rather than simply remembering LeetCode #1.

Final Takeaway

Two Sum is easy—but its lesson is fundamental.

A strong software engineer doesn't immediately jump into writing nested loops.

They ask:

"What information can I remember so I don't have to calculate the same thing again?"

The hash map gives us that memory.

Instead of checking every possible pair:

O(n²)

we can remember what we've already seen and solve the problem in:

O(n)

That transition—from brute force to optimized thinking—is exactly what technical interviews are designed to test.

And this is where our Kairos Coders LeetCode Interview Preparation Series begins.

Next: We'll move beyond Two Sum and start learning another fundamental interview pattern that appears again and again across coding interviews.