Last Updated: 1 Dec, 2021
Smaller Than Triplet Sum
Moderate
Asked in companies
You are given an array ‘ARR’ containing ‘N’ integers, and you are also given an integer ‘TARGET’.
You task is to find the count of triplets i, j, k ( 0 ≤ i < j < k < N ), such that 'ARR[i]' + 'ARR[j]' + 'ARR[j]' is less than the value of ‘TARGET’.
For Example :
If ‘N’ = 7, ‘ARR’ = { 1, 5, 2, 3, 4, 6, 7 } and ‘TARGET’ = 9
Then, there are three triplets with sum less than 9:
1) {1, 5, 2}
2) {1, 2, 3}
3) {1, 2, 4}
4) {1, 3, 4}
Thus, the output will be 4.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’, denoting the size of the array.
The second line of each test case contains 'N' integers ‘ARR’, denoting the array elements.
The third line of each test case contains a single integer ‘TARGET’, denoting the target value to evaluate the smaller sum.
Output Format :
For each test case, print the count of triplets having a sum less than the given target value.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ 'T' ≤ 10
1 ≤ 'N' ≤ 100
-100 ≤ 'ARR[i]' ≤ 100
-100 ≤ 'TARGET' ≤ 100
Time Limit: 1 sec
Approaches
We can simply run three loops and generate all the possible triplets, for each triplet we can then check if its sum is less than the given target value, we can finally return the count of triplets that had a sum less than the target value (Standard Brute Force Approach!).
The steps are as follows :
- Initialize a variable ‘count’ equal to 0, this will store the count of valid triplets.
- Run the outermost FOR loop for variable ‘i’ from 0 to ‘N’ - 1, run the middle FOR loop for variable ‘j’ from ‘i’ + 1 to ‘N’ - 1 and run the innermost loop FOR loop for variable ‘k’ from ‘j’ + 1 to ‘N’ - 1:
- For the triplet ARR[i], ARR[j], ARR[k], calculate its sum, and if it is less than ‘TARGET’ then increment the value of ‘count’ to include the generated triplet in answer.
- Finally, return the value of ‘count’.
An initial precomputation cost of sorting the input array can help us solve this problem quickly, after sorting the array we can generate all the pairs, and for each generated pair we can find the third number for its triplet using the simple binary search.
For each generated pair (ARR[i], ARR[j]), we can find the third number ARR[k] such that ARR[k] is greatest and the following property holds true: ARR[i] + ARR[j] + ARR[k] < Target, once we have found such an ARR[k] we can conclude that all the numbers lying between the indices [j+1, k] will also satisfy the property: ARR[i] + ARR[j] + ARR[k] < Target, (that’s the reason we sorted the array initially).
The steps are as follows :
- Sort the input array.
- Initialize a variable ‘count’ equal to 0, this will store the count of valid triplets.
- Run the outer FOR loop for variable ‘i’ from 0 to N - 1 and run the inner loop FOR loop for variable ‘j’ from ‘i’ + 1 to ‘N’ - 1:
- For each generated pair ‘ARR[i]’ and ‘ARR[j]’ calculate its sum and store it in the variable ‘pairSum’.
- Apply binary search to find the index ‘k’ such that ‘pairSum’ + ‘ARR[k]’ < ‘TARGET’ and also the value of ‘ARR[k]’ is maximum possible.
- Add the value of ‘k’ - ‘j’ to ‘count’ as all the elements lying on the indices lying between [ ‘j’ + 1, ‘k’ ] can be used as the third number with the current pair, just make sure that you don’t add a negative value to ‘count’, this is because ‘j’ should be less than ‘k’.
- Finally, return the value of ‘count’.
An initial precomputation cost of sorting the input array can help us solve this problem quickly. Let us see how this works.
Let’s discuss a simpler version of this problem first and then extend the logic to this one. Consider the case where we are asked to find the number of pairs in the array with their sum less than some given target value. One can easily approach this problem using the two-pointer approach in linear time complexity, we can sort the array and then initialize two pointers one marking the start and one marking the end of the current search space. The start pointer marks the first element of our pair and we need to adjust the end pointer such that the sum of elements corresponding to the start and end pointer is less than the target value and the value of the end is as large as possible
Using this we can conclude that all the elements lying between [start+1, end] can be the second element of the pair when the first element is the element corresponding to the start pointer. Note that we don’t have to adjust the end pointer to point to the last element of the sorted element each time, we can just continue our search considering the logic that the next element pointed by the start pointer will be smaller than the previous one which means the element corresponding to the end will never lie to the right of the current position of the end pointer, in short, this means that we have to move the start pointer only to the right and end pointer only to the left (standard 2-pointer approach!).
Extending this logic further, if we fix the first element of our triplet and find the remaining two elements with the target value now equal to Target - ARR[i] where the first element of the triplet is ARR[i]. That is, we can now apply the same approach discussed above to find the other two elements of the triplets using the updated value of the target.
The steps are as follows :
- Sort the input array.
- Initialize a variable ‘count’ equal to 0, this will store the count of valid triplets.
- Run a FOR loop for variable ‘i’ from 0 to N - 1, ARR[i] denotes the first element of the current triplet, inside the loop:
- Initialize ‘st’ equal to ‘i’ + 1 and ‘en’ equal ‘N’ - 1.
- Store the value ‘TARGET’ - ‘ARR[i]’ in the variable ‘updTarget’.
- Run a while loop till ‘st’ is less than ‘en’, inside the loop:
- Decrement the value of ‘en’ till ‘ARR[st]’ + ‘ARR[en]’ >= ‘updTarget’.
- Add the value ‘en’ - ‘st’ to ‘count’ as for the triplets whose first element is ‘ARR[i]’ and the second element is ‘ARR[st]’ there can be exactly ‘en’ - ‘st’ elements that can be used as the third element of the triplet.
- Increment the value of ‘st’.
- Finally, return the value of ‘count’.
Similar problems