Three-Number Sum or Triplet Sum

Lately, I've been focusing on a few algorithm problems every day. I've decided to write out my thought process. This helps me internalize the methods I used in the problem. It's a great way for me to do some self-study and gain a deeper understanding of the problem at hand. I hope that anyone reading this can take something away from my thought process. So here we go!

Problem:
Give an array and a sum, find all sets of three numbers that add up to the sum.

For example:
array = [0, 1, 2, 3, 5, 7, 10]
sum = 12
answer = [ [7, 3, 2], [0, 2, 10], [0, 5, 7] ]

Step 1: Thought Process / Set up

Is the array sorted? If not, I will sort the array.

With sorted arrays, I like to utilize pointers

Loop through the array with a for loop

Move pointers using if statements inside the loop

Step: 2: Function Set Up

def triplet(array, sum);
  array.sort()
  three_sum = []
  for :
    if
    elif
  return three_sum

Here is the basic outline of the problem we will solve. We define a function with parameters of an array and sum. I use the basic sorting method to sort the array. I set up an empty list that we will add our three number sum to.

Step 3: For loop

Now that I have the skeleton of the problem, we can start filling out the rest.

for i in range(len(array)-2):
  left = i + 1
  right = len(array) - 1

Because we are looking for a three number sum, we will loop through the array at index i. At the same time, we will have left and right pointers that will start one index to the right of i (index), and at the end of the array.

The left and right pointers will shift depending on where our current total is compared to our sum.

This becomes really intuitive because our array is sorted. Our pointers will start at the positions below. The current total is 19. If our target is 23, then we have to move our pointers. We know that the array is sorted and we know that we need to increase our total. Because of this, we will move our pointer left to the right one index!

array = [ 1, 3, 5, 8, 10, 15]
          i  L            R

array = [ 1, 3, 5, 8, 10, 15]
          i     L          R

#a more times through the loop later...

array = [ 1, 3, 5, 8, 10, 15]
          i  L            R

array = [ 1, 3, 5, 8, 10, 15]
                i  L   R   

With that same logic, if our total gets too big, we will move our right pointer to the left! We will continue this process until we land on our potential sum. What happens if the right pointer crosses over the left? Well, then we will start revisiting the same combinations of numbers. This is inefficient and would give us incorrect results. For that purpose, we will set up a while loop inside the for loop.

Now, lets start putting more of the problem together:

def triplet(array, sum):
  array.sort()
  three_sum = []
  for i in range(len(array)-2): 
    left = i + 1
    right = len(array)-1
    while left < right:
      potential_sum = array[i] + array[left] + array[right]
      if
      elif
      elif
   return three_sum

We are almost there now. Just the if/else logic left. If the potential sum is equal to our given sum, then we will add it to our empty array of three number sums. If it is less than or greater than, we will move our pointers accordingly.

Step 4: if/else logic

if potential_sum == sum:
  three_sum.append(array[i], array[left], array[right])
elif potential_sum < sum:
  left += 1
elif potential_sum > sum:
  right -= 1

....but we made a small mistake. Once we arrive at our sum, we need to keep checking for more sets of three number sums. We need to move the pointers in that case as well.

Step 5: Put it all together

def triplet(array, sum):
  array.sort()
  three_sum = []
  for i in range(len(array)-2): 
    left = i + 1
    right = len(array)-1
    while left < right:
      potential_sum = array[i] + array[left] + array[right]
      if potential_sum == sum:
        three_sum.append(array[i], array[left], array[right])
        left += 1
        right -= 1
      elif potential_sum < sum:
        left += 1
      elif potential_sum > sum:
        right -= 1
   return three_sum

And there we have it! That's our three number sum.

I'll be posting a few times a week with algo problems. Feel free to follow along!