Count Triplets With Given Sum In Sorted Array In C++ Program

In this article, you will learn how to efficiently count all unique triplets within a sorted array that sum up to a specific target value using C++. We will explore both a straightforward brute-force approach and a more optimized method that leverages the sorted nature of the array.

Problem Statement

Given a sorted array of integers arr and a target integer sum, the goal is to find the total number of unique triplets (arr[i], arr[j], arr[k]) such that i < j < k and arr[i] + arr[j] + arr[k] == sum. The array is guaranteed to be sorted in non-decreasing order. This problem is common in areas requiring data analysis or subset sum computations, where finding specific combinations within ordered datasets is crucial.

Example

Consider the sorted array arr = [1, 2, 3, 4, 5, 6] and sum = 9.

A possible triplet is (1, 2, 6) because 1 + 2 + 6 = 9. Another triplet is (1, 3, 5) because 1 + 3 + 5 = 9. And (2, 3, 4) because 2 + 3 + 4 = 9.

The expected count of triplets for this example is 3.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, you should have a basic understanding of:

• C++ Fundamentals: Variables, data types, for loops, while loops, conditional statements (if/else).
• Arrays/Vectors: How to declare, initialize, and access elements in C++ arrays or std::vector.
• Basic Time Complexity: Understanding Big O notation (e.g., O(n), O(n^2), O(n^3)) for algorithm efficiency.

 

Relevant Imports/Setup: You will need to include the header for input/output operations and if using std::vector for the array.

Use Cases or Case Studies

Counting triplets with a given sum in a sorted array has several practical applications:

• Financial Analysis: Identifying three specific financial transactions or stock prices that collectively reach a target value, which might indicate a particular market event or arbitrage opportunity.
• Inventory Management: Finding three distinct product units whose combined weight or volume matches a specific container capacity for optimal packing.
• Game Development: In puzzle games or strategy games, determining combinations of three resource items that combine to form a more powerful item or fulfill a quest requirement.
• Data Validation: In scientific or engineering data, checking if three sensor readings or experimental values consistently sum to an expected theoretical total, indicating system calibration or data integrity.
• Cryptography: As a sub-problem in certain cryptographic algorithms or challenges involving number theory, where finding specific sums of elements is a step in a larger process.

 

Solution Approaches

We will explore two distinct methods: a brute-force approach and a more efficient two-pointer approach tailored for sorted arrays.

1. Brute Force Approach

One-line summary: Iterate through all possible combinations of three distinct elements and check if their sum equals the target.

This is the most straightforward method. It involves using three nested loops to pick every possible triplet from the array and then checking if their sum matches the target sum.

// Count Triplets Brute Force
#include <iostream>
#include <vector> // Required for std::vector
using namespace std;

int main() {
    // Example array and sum
    vector<int> arr = {1, 2, 3, 4, 5, 6};
    int sum = 9;
    int n = arr.size();
    int count = 0;

    // Step 1: Iterate through the first element of the triplet
    for (int i = 0; i < n - 2; ++i) {
        // Step 2: Iterate through the second element of the triplet
        for (int j = i + 1; j < n - 1; ++j) {
            // Step 3: Iterate through the third element of the triplet
            for (int k = j + 1; k < n; ++k) {
                // Step 4: Check if the sum of the triplet equals the target sum
                if (arr[i] + arr[j] + arr[k] == sum) {
                    count++;
                }
            }
        }
    }

    cout << "Brute Force: Number of triplets with sum " << sum << " is: " << count << endl;

    return 0;
}

Run

Sample Output:

Brute Force: Number of triplets with sum 9 is: 3

 

Stepwise Explanation:

1. Initialize count to 0 to store the number of triplets found.
2. The outer loop (i) picks the first element arr[i]. It runs from index 0 up to n-3 (to ensure at least two elements remain after arr[i]).
3. The middle loop (j) picks the second element arr[j]. It starts from i + 1 (to ensure distinct elements and i < j) and runs up to n-2.
4. The inner loop (k) picks the third element arr[k]. It starts from j + 1 (to ensure distinct elements and j < k) and runs up to n-1.
5. Inside the innermost loop, check if arr[i] + arr[j] + arr[k] is equal to sum.
6. If the sum matches, increment count.
7. After all loops complete, count holds the total number of triplets.

 

This approach has a time complexity of O(n^3), which can be inefficient for large arrays.

2. Two-Pointer Approach (Optimized)

One-line summary: Fix one element and use a two-pointer technique on the remaining sorted sub-array to find pairs that sum to the required value.

This approach significantly improves efficiency by leveraging the sorted property of the array. For each element arr[i] chosen as the first element of the triplet, we need to find two other elements arr[left] and arr[right] in the remaining sub-array (from i+1 to n-1) such that arr[left] + arr[right] equals sum - arr[i]. The two-pointer technique is perfect for finding pairs in a sorted array.

// Count Triplets Two-Pointer
#include <iostream>
#include <vector> // Required for std::vector
#include <algorithm> // Required for std::sort (if array wasn't guaranteed sorted)
using namespace std;

int main() {
    // Example array and sum (must be sorted)
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Example with more elements, adjust sum for testing
    int sum = 18; // Example sum
    int n = arr.size();
    long long count = 0; // Use long long for count if results can be large

    // Step 1: Iterate through the first element of the triplet
    // This element 'i' is fixed, and we search for two other elements (left, right)
    for (int i = 0; i < n - 2; ++i) {
        // Step 2: Initialize two pointers for the remaining sub-array
        int left = i + 1; // Pointer for the start of the sub-array
        int right = n - 1; // Pointer for the end of the sub-array

        // Calculate the target sum required from the two pointers
        int target_pair_sum = sum - arr[i];

        // Step 3: Use the two-pointer technique to find pairs
        while (left < right) {
            int current_pair_sum = arr[left] + arr[right];

            if (current_pair_sum < target_pair_sum) {
                left++; // Sum is too small, move left pointer right to increase sum
            } else if (current_pair_sum > target_pair_sum) {
                right--; // Sum is too large, move right pointer left to decrease sum
            } else { // current_pair_sum == target_pair_sum
                // Found a triplet: (arr[i], arr[left], arr[right])
                // Now, handle duplicates to count all valid triplets
                if (arr[left] == arr[right]) {
                    // If both pointers point to the same value,
                    // all elements from left to right are identical.
                    // Any two of these can form a pair with arr[i].
                    // Number of pairs = k * (k - 1) / 2 where k = right - left + 1
                    long long k = right - left + 1;
                    count += (k * (k - 1)) / 2;
                    break; // No more unique pairs for this arr[i]
                } else {
                    // arr[left] and arr[right] are distinct but sum to target.
                    // Count occurrences of arr[left] and arr[right] to find all combinations.
                    int count_left_duplicates = 1;
                    while (left + 1 < right && arr[left] == arr[left + 1]) {
                        count_left_duplicates++;
                        left++;
                    }

                    int count_right_duplicates = 1;
                    while (right - 1 > left && arr[right] == arr[right - 1]) {
                        count_right_duplicates++;
                        right--;
                    }
                    
                    count += (long long)count_left_duplicates * count_right_duplicates;
                    left++; // Move left pointer past duplicates
                    right--; // Move right pointer past duplicates
                }
            }
        }
    }

    cout << "Two-Pointer: Number of triplets with sum " << sum << " is: " << count << endl;

    return 0;
}

Run

Sample Output: For arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and sum = 18:

Triplets: (1, 7, 10) (1, 8, 9) (2, 6, 10) (2, 7, 9) (3, 5, 10) (3, 6, 9) (3, 7, 8) (4, 5, 9) (4, 6, 8) (5, 6, 7)

Two-Pointer: Number of triplets with sum 18 is: 10

 

Stepwise Explanation:

1. Initialize count to 0. If the array is not guaranteed sorted, sort it first (e.g., std::sort(arr.begin(), arr.end());).
2. The outer loop (i) iterates from 0 to n-3, fixing arr[i] as the first element of the triplet.
3. Inside the outer loop:
   • Initialize left to i + 1 and right to n - 1. These are the two pointers for the sub-array.

• Calculate target_pair_sum = sum - arr[i]. This is the sum that arr[left] and arr[right] need to achieve.

1. Use a while (left < right) loop for the two-pointer technique:
   • If arr[left] + arr[right] < target_pair_sum, increment left. This is because the current sum is too small, and moving left to a larger value will increase the sum.

• If arr[left] + arr[right] > target_pair_sum, decrement right. The current sum is too large, so moving right to a smaller value will decrease the sum.
• If arr[left] + arr[right] == target_pair_sum, a valid pair is found. Now, we must carefully count all such pairs, especially if duplicates exist:
• Case 1: arr[left] == arr[right]: This means all elements between left and right (inclusive) are identical. Any two of these can form a pair with arr[i]. If there are k = right - left + 1 such elements, the number of pairs is k * (k - 1) / 2. Add this to count and break the inner while loop, as no further distinct pairs can be formed for this arr[i] with these values.
• Case 2: arr[left] < arr[right]: The elements are distinct. We need to count how many times arr[left] appears consecutively starting from left (count_left_duplicates) and how many times arr[right] appears consecutively ending at right (count_right_duplicates). The number of new triplets added is count_left_duplicates * count_right_duplicates. Then, left is moved past its duplicates, and right is moved past its duplicates to continue searching for other pairs.

1. After the outer loop finishes, count will hold the total number of triplets.

 

This optimized approach has a time complexity of O(n^2), which is a significant improvement over O(n^3) for larger inputs.

Conclusion

Counting triplets with a given sum in a sorted array is a classic problem that highlights the power of algorithms leveraging data structure properties. While a brute-force approach is simple to understand, its O(n^3) complexity makes it impractical for larger datasets. The two-pointer approach, with its O(n^2) complexity, provides a much more efficient solution by skillfully utilizing the sorted nature of the array, demonstrating how a small change in methodology can lead to substantial performance gains.

Summary

• Problem: Find triplets (a, b, c) in a sorted array that sum to a target S.
• Brute Force:
• Uses three nested loops.
• Time Complexity: O(n^3).
• Simple to implement but inefficient.
• Two-Pointer Approach (Optimized):
• Iterate through each element arr[i] as the first component.
• Use two pointers (left and right) in the remaining sub-array to find arr[left] and arr[right] such that arr[left] + arr[right] = S - arr[i].
• Handles duplicates carefully to ensure accurate counting of triplets.
• Time Complexity: O(n^2).
• Significantly more efficient for large arrays due to leveraging the sorted property.