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 <= 10³
• -10⁵ <= any element of the input list <= 10⁵
• -10⁹ <= target number <= 10⁹

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:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.