Three Ways to Solve the Two Number Sum Problem

Given an array of integers nums and an integer targetSum, return two numbers such that they add up to targetSum

Input: nums = [2,7,11,15], targetSum = 18

Output: [7,11]

Method 1: Using Two For Loops

This is a naive approach in which we will be using two nested loops and checking if at any point they are equal to ourtargetSum.

def twoNumberSum(nums, targetSum):
  for i in range(len(nums)-1):
    for j in range(i+1,len(nums)):
      if targetSum == nums[i]+nums[j]:
        return [nums[i],nums[j]]
  return []

For every element in the given array nums we will check with other elements present whether the sum of both of the element equals to our targetSum. In case we don’t find any pair we will return an empty array.
The below GIF gives an idea of how the two nested loops are going to be iterated.

Time Complexity: O(n²)
Space Complexity: O(1)

Method 2: Using a Dictionary

This method is the most efficient one.

def twoNumberSum(array, targetSum):
  nums = {}
  for num in array:
    match = targetSum - num
    if match in nums:
      return [match, num]
    else:
      nums[num] = True
  return []

• We will first create an empty dictionary nums .
• Then we will iterate for every element in the array.
• We know our targetSum is equal to the sum of two elements in the array which in this case are num and match .
• So, while iterating we will check whether an element’s complement, let’s saymatch = targetSum — num , is present in our dictionary nums or not.
• If it is not present then we will add it to our dictionary nums
• As soon as we find our match in nums we will return the numbers.

Time Complexity: O(n)
Space Complexity: O(n)

Method 3: Using Sliding Window Approach

This method uses a two-pointer sliding window approach.

def twoNumberSum(nums, targetSum):
  nums.sort()
  left = 0
  right = len(nums)-1
  while left < right:
    match = nums[left] + nums[right]
    if match == targetSum:
      return[nums[left], nums[right]]
    elif match < targetSum:
      left += 1
    elif match > targetSum:
      right -= 1
  return []

• Sort the array using python’s inbuilt sortmethod. It will have a time complexity of O(nlog(n)).
• Then initialize two variables, one pointing to the beginning of the array left = 0 and other to the end of the array right = len(nums)-1
• Create a temp variable match and store the sum of the left and right elements in it.
• Loop till left < right and check if match equals to the targetSum
• If matchis less than to our targetSum increment the leftpointer.
• Else decrement the right pointer.

Time Complexity: O(nlog(n))
Space Complexity: O(1)

Thank you for reading

You can connect with me on Twitter, LinkedIn, and Github.