3 Sum Smaller Problem Statement
Given a list of numbers, count the number of triplets having a sum less than a given target.
Example One
{
"target": 4,
"numbers": [5, 0, -1, 3, 2]
}
Output:
2
{numbers[1], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[4]} are the triplets having sum less than 4.
Example Two
{
"target": 7,
"numbers": [2, 2, 2, 1]
}
Output:
4
{numbers[0], numbers[1], numbers[2]}, {numbers[0], numbers[1], numbers[3]}, {numbers[0], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[3]} are the triplets having sum less than 7.
Notes
The original array's indexes identify a triplet. Therefore, any two triplets will differ if they are denoted by a different triplet of indexes, even if the values present at those indexes are the same. Please observe Example Two for more details on this.
Constraints:
- 3 <= size of the input list <= 103
- -105 <= any element of the input list <= 105
- -109 <= target number <= 109
Code For 3 Sum Smaller Solution: Two Pointer
/*
Asymptotic complexity in terms of length of the input list \`n\`:
* Time: O(n * n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
int count_triplets(int target, vector<int> &numbers) {
sort(numbers.begin(), numbers.end());
int n = numbers.size();
int result = 0;
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1;
while (low < high) {
int triplet_sum = numbers[i] + numbers[low] + numbers[high];
if (triplet_sum < target) {
result += high - low;
low++;
}
else {
high--;
}
}
}
return result;
}
We hope that these solutions to the 3 sum smaller problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
.png)
