EASY
DATA STRUCTURES AND ALGORITHMS

# How to solve the Two Sum Problem

ARRAYSSEARCHHASH TABLES
Written By Tom Wagner Dominic Platt

## Introduction Two Sum

The Two Sum problem involves finding two numbers in an array that add up to a given target number. This is a classic problem whose solution progresses naturally from a less efficient, iterative approach, to a more efficient algorithm enabled through the use of sorting and hashing data structures.

## Problem Two Sum

Given an array of integers, return the indices of the two numbers that add up to a given target.

### Example Inputs and Outputs

#### Example 1

Input: nums = [5, 2, 3], target = 8 Output: [0, 2]

#### Example 2

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

#### Example 3

Input: nums = [5, 5], target = 10 Output: [0, 1]

Constraints

• There is always exactly one solution

## Solution Two Sum

Watch Someone Solve Two Sum
Advance this person to the next round?  Technical Skills:
4/4
Problem Solving Ability:
4/4
Communication Ability:
4/4

### Two Sum Approaches

#### Approach 1: Brute Force

We need to find the combination of which two numbers add up to a given target. We can split this into two steps: 1.) Iterate over every possible pair of numbers 2.) Check if a given pair sums up to our target.

How do we iterate over every pair of numbers? We can start with the first number and compare it against every other number in the array. Then we move the next number and compare it against every other number and so on until we have found our solution.

We can then easily check if a given pair adds up to our target. If it does then we have found our solution and we can return the two indices. From the diagram, we can see this approach in action. Where `i` and `j` represent the index pairs. On each iteration, we calculate the sum and see if it is equal to our target. Notice how `j` is never behind `i`, which ensures that we never re-evaluate already evaluated sums.

#### Two Sum Python and JavaScript Solution - Brute Force

``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 1. Iterate over every possible number pair
for i in range(len(nums)):
# j is always ahead of i so that we don't re-evaluate already evaluated sums
for j in range(i+1, len(nums)):
# 2. Check if a given pair adds up to our target
if nums[i] + nums[j] == target:
# Return the indices when a pair has been found
return i, j``````

#### Time / Space Complexity Analysis

• Time Complexity: `O(n<sup>2</sup>)`, where `n` is the size of the array. For each number, we have to evaluate every other number in the array.

• Space Complexity: `O(1)`, disregarding the input, all other variables have constant space.

#### Approach 2: Hash Table

We can build on the brute force solution and see that there is a lot of repeated work. This is because we iterate over the array multiple times.

Why do we need to iterate multiple times? For each number, we try to find another number which sums to the target. We refer to this other number as the "complement", and to find this number we check every other element in the array.

We can rephrase the previous algorithm: 1.) Iterate over every number in the array 2.) For each number scan the rest of the array to see if there is another number which sums to the target.

Notice how we repeatedly search the array for this "complement" number (step #2 above), which takes `O(n)` time. Is there some way we can do this step faster?

We can reduce this repeated work by using a hash table. A hash table is a data structure which stores key-value pairs, a value can be looked up with a given key in constant time. We can store a number with its index in the hash table. Then when we need to check if the complement number is in the array, we can do so in constant time.

With this in mind we can break down our hash table algorithm into steps:

1.) Iterate over every number in the array This can be done with a simple for loop.

2.) Calculate the complement The complement is the other number that would sum to the target and can be calculated as `target - num`.

3.) Check if that complement is in our hash table If the complement is in the hash table then we can look up its index and we have our solution! If it is not then we continue to search the array.

4.) Add the current number to our hash table The current number may sum up with another number that we have not yet evaluated. We can store the number in the hash table as a key with the index as the value for future checks. From the diagram, we can see how the hash table is modified and evaluated through each iteration until we find a sum.

#### Two Sum Python and JavaScript Solution - Hash Table

``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# Our hash table that stores at which index the number is at
numToIndex = {}

# 1. Iterate over every number in the array
for i in range(len(nums)):
# 2. Calculate the complement that would sum to our target
complement = target - nums[i]

# 3. Check if that complement is in our hash table
if complement in numToIndex:
return numToIndex[complement], i

# 4. Add the current number to our hash table
numToIndex[nums[i]] = i``````

#### Time/Space Complexity

• Time Complexity: `O(n)`, where `n` is the size of the array. We iterate over every number in the array and the hash table lookup/add operations take constant time.
• Space Complexity: `O(n)`, where `n` is the size of the array. Our hash map stores every number in the input array.

## Practice Questions Similar to Two Sum

MEDIUM
Data Structures and Algorithms
Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

Watch 1 interview
MEDIUM
Data Structures and Algorithms
Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

Watch 1 interview
EASY
Data Structures and Algorithms