The Two Sum problem is one of the most popular coding interview questions and is also the first problem on LeetCode. Although it looks simple at first, it introduces an important concept that appears in many interview questions: using a Hash Map (Dictionary) to improve performance.

In this article, we'll solve the problem using Python, understand the logic behind the solution, walk through an example, and analyze its time and space complexity.

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.

You can assume that each input has exactly one solution, and you may not use the same element twice.

Example

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

Output:
[1, 0]

Because:

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

Brute Force Approach

The simplest solution is to compare every number with every other number.

For every element, check all remaining elements until you find a pair whose sum equals the target.

Although this method works, it is inefficient because it requires checking many unnecessary pairs.

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

For large arrays, this approach becomes slow.

Optimized Approach (Hash Map)

Instead of checking every possible pair, we can use a dictionary (Hash Map) to remember the numbers we've already visited.

Here's the idea:

• Visit each number only once.
• Calculate the number needed to reach the target.
• Check if that number already exists in the dictionary.
• If it does, we've found our answer.
• Otherwise, store the current number and continue.

Since dictionary lookups take constant time on average, this makes the solution much more efficient.

Intuition

Imagine you're solving the problem while reading the array from left to right.

Whenever you see a number, ask yourself:

"Have I already seen the number that would complete the target?"

If the answer is yes, return both indices.

If not, save the current number for future checks.

This simple idea allows us to solve the problem in just one pass.

Python Solution

class Solution:
    def twoSum(self, nums, target):
        # Dictionary to store numbers and their indices
        seen = {}

        # Traverse the array
        for i in range(len(nums)):

            current = nums[i]

            # Number needed to reach the target
            complement = target - current

            # If complement exists, return both indices
            if complement in seen:
                return [i, seen[complement]]

            # Store current number and its index
            seen[current] = i

Dry Run

Let's understand the algorithm using an example.

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

Step 1

Current Number = 2

Complement = 9 − 2 = 7

Dictionary:

{2: 0}

Step 2

Current Number = 7

Complement = 9 − 7 = 2

Since 2 already exists in the dictionary, we immediately return:

[1, 0]

No further iterations are needed.

Why This Approach Works

The dictionary stores every number we've already processed.

Instead of searching the entire array again, we can instantly check whether the required complement exists.

This reduces the number of operations significantly and makes the solution much faster than the brute-force approach.