The Two Sum problem is one of the most popular coding interview questions. Although it looks simple, it introduces several important concepts that appear repeatedly in algorithm design, such as brute force search, sorting with two pointers, and hash maps.

Let’s break down the problem and progressively improve our solution.

Problem Statement

Given an array of integers nums and an integer target, return the indices i and j such that:

  • nums[i] + nums[j] == target
  • i != j

You can assume:

  • Exactly one valid answer exists.
  • Return the smaller index first.

Example

Input:
nums = [3,4,5,6]
target = 7

Output:
[0,1]

Because:

nums[0] + nums[1] = 3 + 4 = 7

Solution 1: Brute Force

The most straightforward approach is to check every possible pair.

Idea

For every element, compare it with every element that comes after it.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

How it works

Suppose:

nums = [3,4,5,6]
target = 7

The algorithm checks:

3 + 4 = 7 ✅

Since it finds the answer immediately, it returns:

[0,1]

In the worst case, however, it checks almost every pair.

Time Complexity

  • Time: O(n²)
  • Space: O(1)

Although this solution is easy to understand, it becomes slow for larger arrays because of the nested loops.

Solution 2: Sorting + Two Pointers

We can improve the search by sorting the numbers first.

The challenge is that the problem asks for the original indices, so we cannot simply sort the array directly.

Instead, we store each number together with its original index.

A = []

for i, num in enumerate(nums):
    A.append([num, i])

For example:

nums = [3,4,5,6]

becomes

[
    [3,0],
    [4,1],
    [5,2],
    [6,3]
]

After sorting (already sorted in this case), we place two pointers:

  • Left pointer at the smallest number.
  • Right pointer at the largest number.
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        A = []

        for i, num in enumerate(nums):
            A.append([num, i])

        A.sort()

        i, j = 0, len(nums) - 1

        while i < j:
            curr = A[i][0] + A[j][0]

            if curr == target:
                return [
                    min(A[i][1], A[j][1]),
                    max(A[i][1], A[j][1])
                ]
            elif curr < target:
                i += 1
            else:
                j -= 1

        return []

Why do two pointers work?

Since the array is sorted:

  • If the current sum is too small, moving the left pointer right increases the sum.
  • If the current sum is too large, moving the right pointer left decreases the sum.

This lets us eliminate many unnecessary comparisons.

Time Complexity

Sorting dominates the runtime.

  • Time: O(n log n)
  • Space: O(n)

This is much better than brute force, but we can do even better.

Solution 3: Hash Map (Optimal)

Instead of searching for another number every time, we can remember the numbers we’ve already seen.

The key observation is:

If the current number is num, then the number we need is:

complement = target - num

If we’ve already seen the complement, we’ve found our answer.

Algorithm

  1. Create an empty hash map.
  2. Iterate through the array.
  3. Compute the complement.
  4. Check if the complement already exists.
  5. If it does, return the indices.
  6. Otherwise, store the current number and its index.
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}

        for i, num in enumerate(nums):
            complement = target - num

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

            seen[num] = i

Example Walkthrough

nums = [3,4,5,6]
target = 7

Initially:

seen = {}

Step 1

num = 3
complement = 4

4 isn’t in the hash map.

Store:

seen = {
    3: 0
}

Step 2

num = 4
complement = 3

3 is already in the hash map.

Return:

[0,1]

Done.

Only one pass through the array is needed.

Why This Works

The hash map gives us constant-time lookups.

Instead of searching through the remaining elements for every number, we immediately know whether its complement has already appeared.

This reduces the algorithm from quadratic time to linear time.

Complexity Comparison

Solution

Time

Space

Brute Force

O(n²)

O(1)

Sort + Two Pointers

O(n log n)

O(n)

Hash Map

O(n)

O(n)

Key Takeaways

The Two Sum problem is a great example of how recognizing patterns can dramatically improve an algorithm.

  • Brute Force is simple but inefficient.
  • Sorting + Two Pointers improves performance but requires tracking original indices and incurs the cost of sorting.
  • Hash Maps provide the optimal solution by trading extra memory for much faster lookups.

The hash map approach is the one most interviewers expect because it achieves the best possible time complexity of O(n)while keeping the implementation clean and easy to understand.

Understanding why each optimization works is more valuable than memorizing the final solution. Once you recognize the idea of storing previously seen values for constant-time lookup, you’ll start seeing the same pattern in many other interview problems.