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.

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.

Visualizing Method 1
Visualizing Method 1

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

Method 2: Using a Dictionary

This method is the most efficient one.

  • 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.
Visualizing Method 2
Visualizing Method 2

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

Method 3: Using Sliding Window Approach

This method uses a two-pointer sliding window approach.

  • 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
Thank you for reading

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

Coder ⚡ Developer ⚡Writer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store