Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

Two Sum Problem

Explore three methods to solve the Two Sum Problem where you determine if two numbers in an array add up to a target. Understand the brute-force, hash table, and two-pointer techniques, comparing their time and space complexities to improve algorithmic efficiency.

We'll cover the following...

In this lesson, we are going to be solving the “Two-Sum Problem”. Let’s begin by defining the problem. Given an array of integers, return True or False if the array has two numbers that add up to a specific target. You may assume that each input would have exactly one solution.

We investigate three different approaches to solving this problem.

Solution 1

A brute-force approach that takes O(n2)O(n^2) time to solve with O(1)O(1) space where we loop through the array and create all possible pairings of elements.

Implementation

Have a look at the code below:

Python 3.5
# Time Complexity: O(n^2)
# Space Complexity: O(1)
def two_sum_brute_force(A, target):
  for i in range(len(A)-1):
    for j in range(i+1, len(A)):
      if A[i] + A[j] == target:
        print(A[i], A[j])
        return True
  return False
A = [-2, 1, 2, 4, 7, 11]
target = 13
print(two_sum_brute_force(A,target))
target = 20
print(two_sum_brute_force(A,target))

Explanation

The outer loop on line 4 iterates over all the elements in A while the inner loop on line 5 iterates from the next index of i to the last index of A in every iteration of the outer loop. These nested loops help us form all possible pairs of array elements in every iteration. On ...