EasyArrayHash Table

Two Sum

2 approaches, code in every language

You are handed a list of whole numbers called `nums` together with a single number named `target`. Your job is to find the one pair of positions in the list whose values add up exactly to `target`, and then hand back those two positions.

You can safely assume that precisely one such pair exists in the input, so there is never any ambiguity about the answer. Each position may only be used a single time, meaning you cannot pair a number with itself by reusing its index.

Example 1

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

Output: [0,1]

The values at positions 0 and 1 are 2 and 7, and 2 + 7 equals the target 9.

Example 2

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

Output: [1,2]

Adding 2 (position 1) and 4 (position 2) gives 6, which matches the target.

Example 3

Input: nums = [3,3], target = 6

Output: [0,1]

Both entries are 3, and combining the two different positions produces the target 6.

Constraints

2 ≤ nums.length ≤ 10^4
-10^9 ≤ nums[i] ≤ 10^9
-10^9 ≤ target ≤ 10^9
Exactly one valid answer exists.

Brute Force

Try every possible pair of indices and return the pair that sums to the target.

Intuition

The most direct idea is to simply examine each possible combination of two entries. For every element we look at all the elements that come after it, add the two together, and check whether the total matches the target. Since the problem guarantees a unique answer, the first matching pair we find is the one to return.

Algorithm walkthrough

1Walk an outer index `i` across the array from the first element to the last.
2For each `i`, walk an inner index `j` starting just after `i` to the end of the array.
3Compare the sum of `nums[i]` and `nums[j]` against `target`.
4As soon as the sum equals `target`, return the pair `[i, j]`.

Implementation

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

Time

O(n²)

Space

O(1)

One-pass Hash Map

Scan the array once, using a hash map to instantly find the needed complement.

Loading animation…

Intuition

For any element `x`, the partner we need is `target - x`, its complement. Instead of searching for that complement with a second loop, we remember every value we have already seen in a hash map that maps a value to its index. As we pass over each element we ask the map whether its complement has shown up earlier; if it has, we have found the pair in a single scan.

Algorithm walkthrough

1Create an empty hash map that associates each value with the index where it appeared.
2Iterate through the array once, and for the current element `x` compute `target - x`.
3If that complement is already a key in the map, return the stored index paired with the current index.
4Otherwise, record `x` and its index in the map and continue to the next element.

Implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, x in enumerate(nums):
            complement = target - x
            if complement in seen:
                return [seen[complement], i]
            seen[x] = i
        return []

Time

O(n)

Space

O(n)

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Ledger Reconciliation is our own problem on the technique behind Two Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free