Member-only story
Count the Number of Triplets in an Array with Sum within the Given Range [a, b] | Coding Interview | Sorting
This is a medium category problem, and it should serve as a simple introduction to some other techniques for solving problems. And It has been asked by Amazon and SAP Labs.
For a better grasp of the problem, try to code the solution yourself. I have provided the code (properly commented) for reference if you get stuck at any point.
This article is part of the 30 Days Preparation plan for Coding Interviews 😎.
Table of Contents
Description
Given an array of N integers and a range [a, b], find the number of triplets from the given array with sum within the range.
In other words, the sum of all triplets should be greater or equal to a and lesser or equal to b.
Example 1:
Input: [4 8 6 3 2 7], range: [6 12]
Output: 4Explanation: The 4 triplets are [4 6 2], [4 3 2], [6 3 2], and
[3 2 7].Example 2:
Input: [7 4 2 9], range: [14 15]
Output: 1Explanation: The sum of the triplet [4 2 9] is 15 which is within the range [14 15
Next, we will start with the brute force approach that has O(n³) complexity.
Do you want to stay updated on Coding interview tips and new Questions? Please click on subscribe button to get an email when the new tutorial is published.
Brute Force Solution For Finding Triplets
- We want to try each possible triplet from the array; hence we will use 3 nested loops, each loop pointing to a member of the triplet.
- Start a loop pointing to the first element of the input array, i (index) = 0 till i ≤ N-2.
- Another loop (nested) starts from the…
