Find Triplet in Array that sum to a Given Value

Find Triplet in Array that sum to a Given Value

September 3, 2018 Uncategorized 0


In today’s post, I will be discussing an interview question related to arrays. This is similar to my previous post, in which I discussed how to find a pair with a given sum in an array.

Suppose you are given an array.

[1,9,7,6,3,5,2,8] And you are given a targetSum = 10. You have to find if a triplet exists in the array such that the sum is equal to the target sum.

The first thing that comes to mind when looking at the question is the brute force way:

You can start 3 nested loops and check if the sum is equal to the target sum.

for(i = 0 -> arrayLength – 2)

for(j = i+1 -> arrayLength – 1)

for(k = j+1 -> arrayLength)

if(arr[i] + arr[j] + arr[k] == sum)

return true;

end of all for loops

return false

The next thing the interviewer will ask you is the algorithmic complexity of this solution. since it’s 3 nested for loops, the complexity is O(n^3).

Now the interviewer will ask you how can you do better than O(n^3)?

At this point, you should start thinking of a better solution.

The next solution that comes to mind is using a HashSet. You can loop through the array. And then in the second loop, which will be nested, you can check if a pair exists such that their sum is equal to sum-arr[i]. So we have reduced the problem to a pair sum which we have discussed in the previous video here.

for (i = 0 -> arrayLength – 1)

pairSum = sum – arr[i]

for(j = i+1 -> arrayLength)

{if(hashset.Contains(pairSum – arr[j]))

return true;

hashSet.Add(arr[j])

}

at the end of all loops

return false

 

So what is the algorithmic complexity of this solution? Since there are 2 for nested loops and we are using the power of HashSet, we were able to reduce the run time complexity of our solution from O(n^3) to O(n^2).

However, by using a HashSet, we increased the space complexity to O(n).

At this point, if the interviewer has time, he or she may ask you to devise a solution that has same run time complexity but less space complexity.

The next solution with lower space complexity but same run time complexity can be achieved using sorting.

If you sort the whole array beforehand. Start the first for loop. Now inside the for loop, you have to find a pair such that their sum is equal to sum – arr[i]. We have again reduced our problem to find a pair in an array such that their sum is equal to a given value but this time our array is sorted. In order to find a pair such that their sum is equal to a given value in a sorted array, we can use 2 pointers – one at the beginning and other at the end of the array. Check if their sum is equal to what we are looking for. If yes, we found the value. If the sum of the pair is less than what we are looking for, we increment the left pointer. If the sum of the pair is greater than what we are looking for, we decrement the right pointer. Using this method, we can find a pair such that their sum is equal to a given value in O(n) run time.

So overall, what is the complexity of this solution. Since we have to sort the array first, we can use any sorting algorithm. Usually QuickSort is a good choice due to it’s run time complexity of O(n * log(n)) and then there are 2 for loops which is O(n^2). So overall, it’s O(n log(n)) + O(n^2) which i equivalent to O(n^2). The space complexity is O(1) since we are not using any more space.

Sort The array

for (i = 0 -> arrayLength – 1)

pairSum = sum – arr[i]

left = i + 1, right = arrayLength – 1

while(left < right)

if(arr[left] + arr[right] == pairSum)

return true

if(arr[left] + arr[right] < pairSum)

left ++

if(arr[left] + arr[right] > pairSum)

right —

end of all loops

return false

 

At this point, if the interviewer likes your solution, he or she might ask you to code it on the whiteboard. Before you jump on to code it, please make sure you think about edge cases and write them down on the whiteboard. Here is the GitHub link for the actual code.

At the end, you should test the code with an example and make sure it’s doing what you intend it to do. If you follow all these steps you will have successfully answered the interview question.

I hope you liked the video and it helps you to crack technical interviews. I will be adding more such interview questions to my youtube channel in future. So please subscribe here.