Unfold KSum Family Problems
Chapter 1: A Deeper Look Into Two Pointers Approach.
Table of Contents
1. Introduction
Finally, It is the weekend. It has been a long week for you. You cleaned the house and bought some groceries for dinner. But, this dinner was not like other dinners; because your high school friends would come over to join you. One hour later, your friends arrived, and your childhood sweetheart was there! She was the first person you met at the door. You were over the moon seeing her. You had short talks before you started eating.
After finishing dinner, your childhood sweetheart suggested playing the “Guess the food” game. But, this time, instead of guessing the food name, you must name one or more ingredients of this mystery food. You wanted to impress her, so you were thinking of this question:
How can you quickly guess the names of these ingredients before dumping that bucket of ice-cold water on your head?
Let us see how this post can help us develop an efficient approach to finding those ingredients quickly.
We will start this series with KSum Family Problems. One of the most asked questions among interviewers, because It contains multiple solution patterns that you can see among almost any other algorithm problem. Also, it allows the interviewers to easily extend their questions from one type of KSum problem to another version of the KSum problem.
In this type of problem, we are:
Given a list of integers, we want to find all the groups of K numbers that add up to a given target. In such a way, these groups should all be unique.
Mathematically, this could be formalized as:
Alright, let us get started!
2. 1Sum
2.1 Problem Description
This is our first version of KSum, which is considered a search problem, but here we re-define it as the simplest version of KSum. (1-dimension)
In this problem:
We are given a list of unique numbers and want to find the index of a number that matches a given target.
A + 0 = target
2.2 Example
Inputs: nums = [6,2,5,4,11], target = 4
Outputs: index is 3
So here is an example of the inputs for our algorithm and what it should return. If the algorithm receives a list nums = [6,2,5,4,11] and a target = 4, then if this target is found inside the list, the algorithm should return its index, which is here 3.
2.3 Brute Force Solution
A simple solution to this problem is to loop over all the numbers inside the list and look for that target. If we found it, we would return its corresponding index. Ok, here is the code:
def one_sum(nums, target):
n = len(nums)
for i in range(n):
if nums[i] == target: return i
return -1The time complexity for this solution is:
In the worst-case scenario, the target will be found at the end of the list or not exist, and we will iterate over all list numbers.
And the space complexity for this solution will be:
no extra space is used!
2.4 Optimized Solution
Let us assume that our list of numbers is sorted. Then, the time complexity could be reduced to O(log n) using the Binary Search algorithm. But, for the sake of the interdependency of the concepts of the problems in this post, we will discuss another solution.
This solution is much faster than the naive solution in terms of time complexity. Still, the binary search algorithm is better. So now, did you guess this solution?! Yes, exactly; bravo! It is the Two-pointers approach.
The two-pointer approach is considered one of the most popular techniques when you have a search operation in a list ( sorted or not) or a collection. The two-pointer approach’s basic idea is to use two variables instead of one loop variable (pointer) to traverse a list or collection. For this problem, we will apply it as follows:
Initialize two pointers: a left pointer with a value equal to left = 0 and a right pointer with a value equal to right = n-1, where n = array size.
Then, we check if nums[left] == target, then increase the left pointer by 1.
Also, we check if nums[right] == target, then decrease the right pointer by 1.
Here is a visual explanation of how the algorithm works
Here is the actual code:
def one_sum(nums, target):
n = len(nums)
left = 0
right = n-1
while left < right:
if nums[left] == target: return left
if nums[right] == target: return right
left+=1
right-=1
return -1The time complexity is still:
in the worst-case scenario, but compared to the naive approach is much faster because of using two pointers to do the check simultaneously.
The space complexity is
with no extra space.
2.5 Patterns
In this problem, we have the following patterns:
Two Pointers: When you have a search operation in a list ( sorted or not) or a collection, always think about using two pointers approach to fast-traverse that collection.
3. 2Sum
3.1 Problem Description
This is the second member of the KSum family. In this problem:
We are given a list of unique integers and want to find the indices of two numbers that add up to a given target. Given that there is just one unique pair that forms the target.
A + B = target
3.2 Example
Inputs: nums = [6,2,4,3,11], target = 15
Outputs: [2,4] — > nums[2] + nums[4] = 15
This is an example of the inputs and outputs of our algorithm. If the algorithm receives a list nums = [6,2,5,4,11] and a target = 15, then if this target is found inside the list, the algorithm should return the indices of the two numbers that their sum equals that target, which is here 2 and 4.
3.3 Brute Force Solution
The intuitive approach to solving this problem is making two loop variables (i, j). Then, we look for a combination of two numbers that add up to the target value. let’s see how we code this:
def two_sum(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n): # we start the second loop from j = i+1.
if nums[i] + nums[j] == target:
return [i, j]
return []Time Complexity will be:
because we used two nested loops, which will result in this time complexity in the worst-case scenario.
Space Complexity is:
Optimization Opportunity: Even though this algorithm is efficient in terms of space complexity O(1), it is not practical in terms of time complexity. So, can we reduce the time complexity from O(n²) ⇾ O(n)?
3.4 Optimized Solution
One of the most useful data structures that programmers like to use is Hashmap. It has O(1) time complexity for the search operation of almost any element inside it. We can work around the inefficiency of the brute-force solution by relying on space complexity.
Therefore, we can store all the numbers inside a Hashmap. Then we can loop over the list, and at any time, we will query our Hashmap using a key with a value equal to target — nums[i], where i is the loop variable, and nums is the list of numbers. Let’s see how we code this:
def twoSum(nums, target):
mapper = {}
for i, e in enumerate(nums):
# Store the numbers inside the hashmap,
# where the keys are the numbers,
# and the values are the coressponding indicies.
mapper[e] = i
for i in range(len(nums)):
b = target - nums[i] # get the key value
if b in mapper and mapper[b] != i:
# if the key is existed in the hashmap and the its value
# does not equal to the index of the second number, we return
# the indicies.
return (i, mapper[b])Then the time complexity will be:
But the space complexity will be:
Yes, I know, I know! It is a trade-off between optimizing time complexity versus space complexity.
3.5 Patterns
Hashmap: As a rule of thumb, always consider using Hashmap if you want to store intermediate values or optimize a collection’s search time.
4. 3Sum
4.1 Problem Description
This is another version from the KSum problem family. In this problem:
We are given a list of non-unique integers, and we want to find three numbers that add up to zero. In such a way, the triplets should be all unique.
A + B + C = 0
4.2 Example
Input: nums = [-1,0,1,2,-1,-4], target = 0
Output: [ [-1,-1,2], [-1,0,1] ] , not [ [-1,-1,2], [-1,0,1], [1,0,-1],]
This is an example of the inputs and outputs of our algorithm. If the algorithm receives a list nums = [-1,0,1,2,-1,-4] and a target = 0, then if this target is found inside the list, the algorithm should return the indices of the three numbers whose sum equals zero, which are here [ [-1,-1,2], [-1,0,1] ].
4.3 Brute Force Solution
Again, the intuitive approach to solving the problem is making three loops variables (i, j, k). Then, we look for a combination of three numbers that add up to zero. In the code below, notice how the sorting we did initially allowed the Python set “result” to recognize duplicate combinations.
def three_sum_brute(nums):
nums = sorted(nums) # sort nums.
n = len(nums)
target = 0
result = set()
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
combination_sum = nums[i] + nums[j] + nums[k]
if combination_sum == target:
result.add((nums[i], nums[j], nums[k]))
return resultThe time Complexity for this solution is:
because of using three nested loops!
Space Complexity is:
because we use a python set “result” to store the combinations.
Optimization Opportunity: Can we reduce the time complexity from O(n³) ⇾ O(n)?
3.4 Optimized Solution
Again, the answer is yes!, and that is by using the “Two Pointers” approach. The idea is as follows:
Sort the array of integers in increasing order.
Create a set to hold the combinations of triplets called “result.”
While looping over the array using a variable (i)
Initialize two pointers, a left pointer with a value equal to i+1 and a right pointer with a value equal to n-1, where n = array size.
Make a nested loop and traverse the array using the two pointers. Because we are looking for nums[left] + nums[right] + nums[i]= 0, we will set our target = -nums[i].
If nums[left] + nums[right] = target, we will add this to the set of results.
If nums[left] + nums[right] < target, that means we need to increase the left pointer to increase the value of this summation.
Finally, if nums[left] + nums[right] > target, it means we need to decrease the right pointer to decrease the value of the summation and push it toward zero.
In the end, we return the “result.”
Here is how we can code this optimized version of the algorithm:
def three_sum_optimized(nums):
nums = sorted(nums)
n = len(nums)
result = set()
for i in range(n):
left = i + 1
right = n - 1
target = 0 - nums[i]
while left < right:
combination_sum = nums[left] + nums[right]
if combination_sum == target:
result.add((nums[i], nums[left], nums[right]))
left += 1
right -= 1
elif combination_sum < target:
left += 1
else:
right -= 1
return resultThe Time Complexity will be:
Which is a slightly better time complexity compared to O(n³). We used two main operations, Sorting O(n.logn) and Searching O(n²) (two nested loops). However, the time complexity is still O(n²), because O(n.logn) + O(n²) = O(n²).
The Space Complexity will be:
But, it is still similar to the brute force solution. No escape from it!
4.5 Patterns
Sorting: Sorting is one of the most important preprocessing steps when solving an algorithm problem, especially array (list) problems. It makes the problem a lot easier to be breached, so consider for a while sorting your array when you solve an array problem.
Using python “ Set” data structure: Overcome repetitive values using the python “set” data structure. It has the property of performing auto-elimination of duplicate values. Here, I used it to store the combinations while removing the duplicates.
Two-pointers: We used two-pointers to traverse the list faster. Notice how it becomes easier to use this approach after sorting the list values.
5. 4Sum
5.1 Problem Description
This will be our last problem from the KSum family before discussing the generic version of KSum. As you notice, the pattern of solving these problems becomes evident, and I bet you have started to sense it too. So,
Given a list of non-unique integers and a target, we want to find any set of 4 numbers from this list that add up to that target, where those sets are all unique.
A + B + C + D = target
5.2 Example
Input: nums = [3,7,2,4,5,4,6,1,8], target = 12
Output: [[1, 2, 3, 6], [1, 2, 4, 5], [1, 3, 4, 4]]
This is an example of the inputs and outputs of our algorithm. If the algorithm receives a list nums = [3,7,2,4,5,4,6,1,8] and a target = 12, then if this target is found inside the list, the algorithm should return the indices of the three numbers whose sum equals zero, which are here [[1, 2, 3, 6], [1, 2, 4, 5], [1, 3, 4, 4]].
5.3 Brute Force Solution
Like 3Sum, a brute force solution to this problem is to make four loops variables (i, j, k, l). Then, we look for a combination of four numbers that add up to that target value. You see no need to code this solution! It has become a piece of cake now.
5.4 Optimized Solution
The optimized version of 4Sum is very similar to the 3Sum optimized solution. Notice in the code below we just added one more loop (second loop) while keeping the two-pointers loop (third loop). Let us see the code below:
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
result = set()
for i in range(n): # first loop
second_taget = target - nums[i] # target 2
for j in range(i + 1, n): # second loop
third_target = second_taget - nums[j] # target 3
left = j + 1
right = n - 1
while left < right: # third loop
if nums[left] + nums[right] == third_target:
result.add((nums[i], nums[j], nums[left], nums[right]))
left += 1
right -= 1
elif nums[left] + nums[right] < third_target:
left += 1
else:
right -= 1
return resultTime Complexity is:
because we used three loops.
And Space Complexity will be:
As we need to store the results.
6. KSum
Finally, we are meeting with the beast himself! KSum. 2Sum, 3Sum, and 4Sum problems have given us a pattern for solving any KSum problem (i.e., 5Sum, 6Sum)
6.1 Problem Description
To be able to infer the KSum solution from our previous solutions, we need to understand a very important thing first. Any KSum problem can be solved with this simple idea:
Reduce KSum to 2Sum problem, then solve it.
Yes, we need to reduce any KSum to 2Sum, then solve it! But first, to understand this solution pattern, we need to revisit these simple equations:
2Sum problem could be formalized as:
While 3Sum is formalized as:
And 4Sum is formalized as:
Then to solve 4Sum we can rearrange these equations as follows:
Wait, wait, wait, Waleed, I am getting lost. Could you explain more? Absolutely! Let us take 4Sum as an example. We can see that to be able to calculate — let us call it — any lower-degree target (i.e., “t₁”), we need an upper-degree target “t₂” and a “number.” The “number” here represents the 4ₜₕ term in the equation.
Then, to solve 4Sum, we need to calculate these targets starting backwardly, with the uppermost-degree target (i.e., “t₃”), which is always given.
Finally, we can find the last two elements in the equation (a, b) using the two-pointers approach we saw earlier in 2Sum. The good news is that we can apply the exact concept to solve any KSum problem.
6.2 Solution
Here is the summary of the above algorithm:
Starting with the uppermost-degree target (i.e degree = 3, t = “t₃”):
Recursively, calculate the upper-degree targets (t₂, t₁).
When degree = 2, call the 2Sum function to find the last missing elements (a, b).
What on earth are you talking about, Waleed?!!
Alright, alright, here is a visual explanation of how the above algorithm works:
Now, here is the code. For better understanding, connect every line in the code with its corresponding step in the visual illustration above.
def two_sum_2pointers(nums, target):
left = 0
right = len(nums)-1
result = []
while left < right:
if nums[left] + nums[right] == target:
result.append([nums[left], nums[right]])
# ----------- To filter the duplicate cases ---------
while left < right and nums[left] == nums[left+1]: left+=1
while left < right and nums[right] == nums[right-1]: right-=1
#----------------- End of Filtering ----------------
left+=1
right-=1
if nums[left] + nums[right] < target:
left+=1
if nums[left] + nums[right] > target:
right-=1
return result
If we ignore the sorting operation, the time complexity will be:
Where k = degree or the number of missing components, and n = array size.
And Space Complexity is:
ignoring the memory used by the “path” variable.
6.3 Patterns & Tricks
Depth First Search (DFS): We use the Depth-First Search algorithm to traverse the list of numbers by updating the degree (k) and the target values.
Two Pointers: We used the optimized version (with two pointers) of 2Sum To find the last missing elements (a, b).
7. Recap
In this post, we have discussed the KSum problems family. These types of problems have introduced us to some important algorithm patterns that could be summarized as follows:
Problems Patterns:
Problems that require you to look for a set of numbers (subarray) in an array to match a given aggregation value (sum, max, min, …, etc.) → Try to use two pointers. [1][2]
Problems that require finding sets of combinations or solutions subsets → Try using the Depth First Search algorithm (DFS). [3][4]
Solutions Patterns:
For fast item lookup, → Try to use the Hashmap data structure.
To remove duplicates in a list or collection, → Try to use the python set data structure.
8. Next Post
You have just received a $1 million lottery ticket and you have to decide what you want to spend this money on. But, you have many things you wanted to buy and many activities you planned to do. So, you have the following question:
In which order should you accomplish your dreams?
Let us see how the next post will answer this question and help you get the most out of this money, so STAY TUNED!
New to this series?
New to the “Unfold Algorithm Coding Interviews For Data Scientists” series? Start from the beginning, here [link to the series list]
Any oversights in this post?
Please report them through this Feedback Form, I really appreciate that!
Thank you for your reading!
You can learn more about the date of future posts for this series through my newsletter, where I talk about Algorithms, Machine Learning, and Data Science.
If you have any other questions or comments, please do not hesitate to share them with me through Newsletter | Medium | LinkedIn | Twitter. See you soon!
Resources
[1] T. Cormen et al.,
Introduction to Algorithms, 4th edition (2022), The MIT Press.
[2] Amit Singh Rathore, Two Pointers Approach — Python Code (2021), Medium.com.
[3] Educative Answers Team, What is Depth First Search? (2023), Educative.io.
[4] Educative Answers Team, How to implement depth-first search in Python (2023), Educative.io.