Two Sum

Leetcode Link:

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

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

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Method 1: Brute Force#

As with any problem, we always start off with the brute force technique. What is the simplest way to get the answer out, without any concern about the time complexity etc.?

We can simply use 2 for-loops and find out the indices:

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
results = []
for num1 in nums:
for num2 in nums:
if(num1 + num2 == target):
return results

This will give us the right results, but such a method will be a poor solution for a huge array. Though space complexity is in constant time of O(1), with 2 for-loops we have a time complexity of O(n2).

  • Time complexity: O(n2)
  • Space complexity: O(1)

Method 2: Hashing#

To optimise our solution, we simply use a hashtable or dictionary. We trade space for time.

We store the numbers in the array as the keys, with the indices as the corresponding values. Each time we check if a number's complement (i.e. target - number) exists in the hashtable. If yes, we have found a pair! Else, we add it to the hashtable.

The code will look like this:

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

This has a time complexity of just O(n) since we run through the list only once. A space complexity of O(n) exists since we need a hashtable to store the numbers.

  • Time complexity: O(n)
  • Space complexity: O(n)

Modified Question (Sorted Array)#

Finding Just the Possibility#

If we just need to return if a particular sum can be formed from the array, and is the array is sorted, then we can use a 2 pointer method.

We start with 2 pointers, i and j, at the start and end of the array respectively. While i < j, we loop to see if arr[i] + arr[j] == sum. If the result is less than required sum, we increment i. Else if the result is more than the required sum, we increment j. Else, if it is equal, we have found a pair and we return true.

  • Time complexity: O(n)

Using Binary Search (Not recommended)#

If the array is already sorted, one other option is to use binary search. For every element in the array, we can find what is the required complement. Then we can use binary search to see if that number exists in the array.

However, the time complexity for this will be O(n * logn) which is worse than optimal solutions above.

  • Time complexity: O(n * logn)