Two Sum

Easy
easy , array , hash table
04 June 2025
Easy

Two Sum! #

Let’s move on to the first problem — “Two Sum”, one of the most well-known LeetCode questions. Despite its popularity, I’ve actually encountered this task in real interviews. It’s often used as a warm-up, but many engineers only manage to reach the basic brute-force solution.

🔁 Don’t forget the principles we discussed in the previous post!

📄Description #

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Constraints #

Examples #

  • Inputs

    nums = [2,7,11,15]

target = 9

    Output: [0,1] or [1, 0]

    Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

  • Inputs

    nums = [3,2,4]

target = 6

    Output: [1, 2] or [2, 1]

  • Inputs

    nums = [3,3]

target = 6

    Output: [0, 1] or [1, 0]

🐢 Brute Force #

As we discussed in the previous post, let’s not try to jump straight to the most optimized solution. It’s better to start with a working, well-known implementation and improve it step by step.

Also, pay close attention to the problem definition and constraints. One important detail is that there’s a guarantee: every input has exactly one valid answer.

This means we don’t need to handle edge cases or check for multiple solutions — we can safely return the first valid result we find.

In this case, the brute-force solution is straightforward — we need to find a pair of values in a single array that add up to the target. So, we can use two loops: an outer loop (let’s call it i) to pick the first element, and a nested loop (j) to look for a matching pair.

A small trick: we can start the nested loop from the next index (i + 1). This way, we avoid unnecessary comparisons and ensure we don’t return the same element twice.

If the sum of nums[i] and nums[j] equals the target, we’ve found our answer — the pair [i, j].

💻Implementation #

  • package main

func twoSumBruteforce(nums []int, target int) []int {
	for firstIdx, main := range nums {
		for secondIdx, complement := range nums {
			if firstIdx == secondIdx {
				continue
			}
			if main+complement == target {
				return []int{firstIdx, secondIdx}
			}
		}
	}

	return nil
}

  • package main

import (
	"github.com/stretchr/testify/assert"
	"testing"
)

func Test_twoSumBruteforce(t *testing.T) {
	cases := []struct {
		name   string
		nums   []int
		target int
		expRes []int
	}{
		{
			name:   "[2, 7, 11, 15], 9",
			nums:   []int{2, 7, 11, 15},
			target: 9,
			expRes: []int{0, 1},
		},
		{
			name:   "[3, 2, 4], 6",
			nums:   []int{3, 2, 4},
			target: 6,
			expRes: []int{1, 2},
		},
		{
			name:   "[-1, 0], -1",
			nums:   []int{-1, 0},
			target: -1,
			expRes: []int{0, 1},
		},
		{
			name:   "[0, 0], 5",
			nums:   []int{0, 0},
			target: 5,
			expRes: nil,
		},
	}

	for _, testCase := range cases {
		t.Run(testCase.name, func(t *testing.T) {
			res := twoSumBruteforce(testCase.nums, testCase.target)
			assert.Equal(t, testCase.expRes, res)
		})
	}
}

  • export const twoSumBruteForce = (nums: number[], target: number): number[] => {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i !== j && nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }

    return []
}

  • import { twoSumBruteForce } from "./bruteforce";

type TestCase = {
    name: string
    nums: number[]
    target: number
    expRes: number[]
}

const cases: TestCase[] = [
    {
        name: "[2, 7, 11, 15], 9",
        nums: [2, 7, 11, 15],
        target: 9,
        expRes: [0, 1],
    },
    {
        name: "[3, 2, 4], 6",
        nums: [3, 2, 4],
        target: 6,
        expRes: [1, 2],
    },
    {
        name: "[-1, 0], -1",
        nums: [-1, 0],
        target: -1,
        expRes: [0, 1],
    },
    {
        name: "[0, 0], 5",
        nums: [0, 0],
        target: 5,
        expRes: [],
    },
]

describe('twoSumBruteForce', () => {
    cases.forEach(testCase => {
        test(testCase.name, () => {
            const res = twoSumBruteForce(testCase.nums, testCase.target)
            expect(res).toEqual(testCase.expRes);
        })
    })
})

📊 Complexity #

When we talk about complexity, we usually try to estimate two things:

A little spoiler: in most cases, there's a trade-off — we can use more memory to improve speed. And that often makes sense in the real world, since memory is generally cheaper than CPU time.

In our brute-force solution, we compare all possible pairs of values using an outer and a nested loop.

In the worst-case scenario, the first element is compared with the second, third, … all the way to the n‑th element. Then, the second element is compared with the third, fourth, … up to the end, and so on — where n is the length of the input array.

You might notice this forms an arithmetic progression: (n - 1) + (n - 2) + ... + 1

Using the formula for the sum of the first k natural numbers, we get: S = n(n - 1)/2 ≈ (n²)/2

As mentioned earlier, we aim for an approximate estimation — often called the order of growth.

To simplify, we focus only on the dominant term (the one that grows the fastest as n increases) and ignore constants and lower-order terms.

That gives us a final time complexity of: O(n²) or quadratic complexity.

🔍 Rule of thumb:
One nested loop → at least O(n²)
Two nested loops → at least O(n³)
And so on.

And since we don’t use any additional data structures, our brute-force algorithm has constant space complexity — O(1).

⚡ Optimized Solution (with Hash Map) #

Do you remember the Algorithm Designer’s Mantra from Tim Roughgarden?

Can we do better?

Let’s try!

We know that:

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

Now, imagine we could quickly check whether a specific number exists in the array. Then we wouldn’t need a nested loop at all. Instead, for each i, we’d compute:

complement = target - nums[i]

...and simply check if complement exists in the array.

But there’s a catch: arrays don’t give us fast lookups. If we want to check whether a value exists in an array, we have to scan it element by element — that’s still O(n) per lookup, which brings us back to O(n²) in total.

Fortunately, we have a better tool for this: a hash map. This data structure allows us to check for the existence of a value in constant time — O(1).

To be fair, in rare worst-case scenarios — like when many keys collide due to a poor hash function — the performance can degrade to O(n). But if we use a built-in hash map from a modern language without tampering, it will generally provide a uniform distribution and maintain O(1) complexity.

So the idea is simple:

While iterating through the array, we store each number and its index in a hash map — the number as the key and its index as the value. Then, we iterate through the array again and, for each element, check whether its complement exists in the map. If it does — we’ve found the pair.

Now we still have two loops, but they’re not nested — so instead of O(n²), we get O(2n), which simplifies to O(n). In other words, our algorithm now has linear time complexity.

We can do even better by storing values in the hash map and checking for complements in a single loop.

For each element, we first calculate its complement and check whether it already exists in the hash map.

This way, when we encounter the first element of the result pair, its complement has yet to be seen, so we store it.

When we reach the second element, we find that its complement (the first one) is already in the map, and we return the pair!

💻Implementation #

  • package main

func twoSum(nums []int, target int) []int {
	indexMap := make(map[int]int)

	for i, num := range nums {
		complement := target - num
		secondIndex, ok := indexMap[complement]
		if ok {
			return []int{i, secondIndex}
		}
		indexMap[num] = i
	}

	return nil
}

  • package main

import (
	"github.com/stretchr/testify/assert"
	"testing"
)

func Test_twoSum(t *testing.T) {
	cases := []struct {
		name   string
		nums   []int
		target int
		expRes []int
	}{
		{
			name:   "[2, 7, 11, 15], 9",
			nums:   []int{2, 7, 11, 15},
			target: 9,
			expRes: []int{1, 0},
		},
		{
			name:   "[3, 2, 4], 6",
			nums:   []int{3, 2, 4},
			target: 6,
			expRes: []int{2, 1},
		},
		{
			name:   "[-1, 0], -1",
			nums:   []int{-1, 0},
			target: -1,
			expRes: []int{1, 0},
		},
		{
			name:   "[0, 0], 5",
			nums:   []int{0, 0},
			target: 5,
			expRes: nil,
		},
	}

	for _, testCase := range cases {
		t.Run(testCase.name, func(t *testing.T) {
			res := twoSum(testCase.nums, testCase.target)
			assert.Equal(t, testCase.expRes, res)
		})
	}
}

  • export const twoSum = (nums: number[], target: number): number[] => {
    // Создаем объект для отслеживания индексом чисел из массива
    // Также можно использовать new Map(), но объект делает в точности то же самое и с ним немного проще работаь.
    const indexMap: Record<number, number> = {}

    for (let i = 0; i < nums.length; i++) {
        // Рассчитываем второе искомое число
        const complement = target - nums[i]

        // Проверяем, есть ли индекс для этого числа в объекте
        const secondIndex = indexMap[complement]

        // Если индекс для числа уже есть в объекте, значит мы нашли искомую пару
        if (secondIndex > -1) {
            return [i, secondIndex]
        }

        // Если индекс для числа еще не добавлен, то записываем его в объект
        indexMap[nums[i]] = i
    }

    return []
}

  • import { twoSum } from "./solution";

type TestCase = {
    name: string
    nums: number[]
    target: number
    expRes: number[]
}

const cases: TestCase[] = [
    {
        name: "[2, 7, 11, 15], 9",
        nums: [2, 7, 11, 15],
        target: 9,
        expRes: [1, 0],
    },
    {
        name: "[3, 2, 4], 6",
        nums: [3, 2, 4],
        target: 6,
        expRes: [2, 1],
    },
    {
        name: "[-1, 0], -1",
        nums: [-1, 0],
        target: -1,
        expRes: [1, 0],
    },
    {
        name: "[0, 0], 5",
        nums: [0, 0],
        target: 5,
        expRes: [],
    },
]

describe('twoSum', () => {
    cases.forEach(testCase => {
        test(testCase.name, () => {
            const res = twoSum(testCase.nums, testCase.target)
            expect(res).toEqual(testCase.expRes);
        })
    })
})

📊 Complexity #

As we mentioned earlier, the time complexity is now O(n) — linear time.

What about space complexity?

In this solution, we use an additional data structure — a hash map. In the worst-case scenario, the map could store up to n - 1 elements (if the matching pair is found only at the very end).

Just like with time complexity, we focus on the order of growth, so we simplify this to O(n) space complexity.

This is a classic trade-off: we use more memory, but significantly improve performance. In this case, it’s a clear win.

✅ Takeaways #

✍️ Written by Denis Kolpakov LinkedIn

📬 Like this post? Follow @thealgoapp for more!

🚀 Trace the algorithmic path on LeetCode
< Previous Challenge
Next Challenge >