LeetCode 1: Two Sum

Problem Restatement

We are given an array of integers called nums and an integer called target.

We need to find two different positions in the array such that the two numbers at those positions add up to target.

Return the two indices.

The same element cannot be used twice. That means if nums[i] is used as the first number, we need another index j, where i != j.

Input and Output

Example function shape:

def twoSum(nums: list[int], target: int) -> list[int]:
    ...

Examples

Consider this input:

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

We need two numbers that add up to 9.

The first number is 2.

To reach 9, we need:

9 - 2 = 7

The number 7 exists at index 1.

So the answer is:

[0, 1]

Another example:

nums = [3, 2, 4]
target = 6

We try to find two numbers that add up to 6.

2 + 4 = 6.

Their indices are 1 and 2.

So the answer is:

[1, 2]

A tricky example:

nums = [3, 3]
target = 6

Here, 3 + 3 = 6.

But we must use two different elements.

The first 3 is at index 0.

The second 3 is at index 1.

So the answer is:

[0, 1]

First Thought: Brute Force

The most direct way is to try every possible pair.

For each index i, we check every later index j.

If:

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

then we return:

[i, j]

Code:

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        n = len(nums)

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

        return []

This works because it checks every valid pair exactly once.

Problem With Brute Force

The brute force solution checks many pairs.

If the array has n numbers, then for each number we may compare it with many other numbers.

The time complexity is:

O(n^2)

For a small array, this is fine.

For a large array, this becomes slow. We need a way to avoid checking every pair manually.

Key Insight

For each number, we do not need to search the whole array again.

Suppose the current number is:

x = nums[i]

We need another number:

target - x

This needed number is called the complement.

For example:

target = 9
x = 2
complement = 9 - 2 = 7

So while scanning the array, we can ask:

“Have I already seen the complement?”

To answer this quickly, we use a hash map.

The hash map stores:

number -> index

So when we visit a number, we can check in constant time whether its complement appeared before.

Algorithm

Create an empty hash map called seen.

This map will store numbers we have already visited, together with their indices.

Then scan the array from left to right.

For each index i and number num:

1. Compute the complement:

need = target - num

2. Check whether need already exists in seen.

3. If it exists, return:

[seen[need], i]

4. Otherwise, store the current number:

seen[num] = i

The order matters.

We check first, then insert.

This prevents using the same element twice.

For example, with:

nums = [3, 3]
target = 6

At index 0, num = 3.

We need another 3, but seen is still empty.

So we store:

seen[3] = 0

At index 1, num = 3.

We need another 3.

Now seen contains 3, so we return:

[0, 1]

Correctness

We scan the array from left to right.

At each index i, the hash map contains only numbers from earlier indices.

That means every index stored in seen is different from i.

For the current number nums[i], the only value that can form the target is:

target - nums[i]

If this value already exists in seen, then there is an earlier index j such that:

nums[j] = target - nums[i]

Therefore:

nums[j] + nums[i] = target

So returning [j, i] is correct.

If the complement does not exist yet, we store the current number and continue.

Because the problem guarantees exactly one valid answer, eventually the second number of that valid pair will be reached. At that moment, the first number will already be in seen, and the algorithm will return the correct indices.

Complexity

Each lookup in the hash map is expected O(1).

So the full algorithm runs in linear time.

Implementation

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}

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

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

            seen[num] = i

        return []

Code Explanation

We start with an empty dictionary:

seen = {}

This stores numbers we have already passed.

The key is the number.

The value is its index.

for i, num in enumerate(nums):

This gives us both the index and the number.

For every number, we compute the missing number:

need = target - num

If need already exists in seen, then we found the pair:

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

The first index is seen[need].

The second index is the current index i.

If we do not find the needed number, we store the current number:

seen[num] = i

This means future numbers can pair with it.

The final return is only for safety:

return []

The problem says there is exactly one answer, so this line should not be reached for valid LeetCode input.

Testing

We can test the solution with a few important cases.

def run_tests():
    s = Solution()

    assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
    assert s.twoSum([3, 2, 4], 6) == [1, 2]
    assert s.twoSum([3, 3], 6) == [0, 1]
    assert s.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]
    assert s.twoSum([0, 4, 3, 0], 0) == [0, 3]

    print("all tests passed")

run_tests()

Test meaning: