DSAPrep
EasyArrays & Hashing

Two Sum

Given an array of integers nums and an integer target, return 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.

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?
View original on LeetCode ↗

The brute-force way to solve this is to check every pair. The key insight that gets us to the optimal solution: for each number, we already know what its partner needs to be (target - num) — so instead of searching for that partner, we can remember every number we’ve already seen and look it up in O(1).

Brute Force

Time O(n²)Space O(1)

Try every pair (i, j) with i < j and check if nums[i] + nums[j] == target. It’s guaranteed to find the answer because it exhausts every possible pair — but it does redundant work: after checking index 0 against everything, it starts over from index 1 with no memory of what it already computed.

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 []

Tracing nums = [3, 2, 4, 7], target = 9:

i
3
0
j
2
1
4
2
7
3
sum = 5target = 9
1 / 5
comparingresultcurrent

i=0, j=1 → 3 + 2 = 5, not 9. Advance j.

Why it’s slow: for each of the n starting indices we may scan almost the whole rest of the array, giving n + (n-1) + ... + 1 ≈ n²/2 comparisons — quadratic time, and it throws away every sum it computes.

Hash Map (One Pass)

OptimalTime O(n)Space O(n)

Walk the array once. Before inserting the current number, check whether its complement (target - num) was already seen. If it was, we’ve found our pair immediately — no nested loop required. This works because addition is commutative: if nums[i] + nums[j] == target, then whichever of i, j we reach second will find the other already sitting in the map.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}  # value -> index
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []

Same trace, nums = [3, 2, 4, 7], target = 9:

i
3
0
2
1
4
2
7
3
complement = 6

Hash Map

3 → 0
1 / 4
resultcurrent

num=3, complement=9-3=6. Not in map yet — store 3 → 0.

Correctness: every number is checked against all numbers before it in a single pass, so any valid pair (i, j) with i < j is caught the moment we reach j, since nums[i] is already stored.

Complexity: one pass over n elements, each doing an O(1) average-case hash map lookup and insert → O(n) time. The map holds up to n entries → O(n) space. This is optimal: you can’t find the answer without at least looking at every element once.