Two Pointers: Count pairs with sum less than target

Problem Statement:

You are given an array and an target.

You need to find the count of pairs whose sum is strictly less than given target

Example:

Input: arr[] = [7, 2, 5, 3], target = 8
Output: 2 

consider the sub array(2, 5) and (2, 3) both are less than the target.

Hence the result is 2

Solution 1: Brute force approach

In this approach, you will generate all possible pairs using 2 nested for loops.

Then count whose pair sum is less than the target.

Time Complexity: O(n^2)

Space Complexity: O(1)

Solution 2: Two pointers approach

Sort the array

Then use the two pointer approach to find the number of pairs with a sum less than the given target.

Initialize 2 pointers one at the beginning and other at the end of the array.

Then compare the sum of elements pointed by the pointers with the target.

If sum < target:

We add (right-left) to the count and move the left pointer one step to the right to explore more pairs.

Because the pairs formed by the left pointer, with every element between left and right will have a sum less than the target.

If sum >= target:

Move the right pointer one step to the left to reduce the sum.

Time Complexity: O(n*logn+n)

Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution_1(vector<int> &arr, int target) 
{

    int count = 0;
    
    for(int i = 0; i < arr.size(); i++) 
    {
        
        for(int j = i + 1; j < arr.size(); j++) 
        {
        
            if(arr[i] + arr[j] < target)
                count++;
        }
    }
    
    return count;
}

int solution_2(vector<int> &arr, int target) {
  
  	sort(arr.begin(), arr.end());

    int left = 0, right = arr.size() - 1;
    int count = 0;
    
    while(left < right) {
        
        int sum = arr[left] + arr[right];
        
        if (sum < target) {
            count += right-left;
            left++;
        }
        else {
            right--;
        }
    }
    
    return count;
}

int main() 
{
	vector<int> arr = {2, 1, 8, 3, 4, 7, 6, 5};
    int target = 7;
    cout << solution_1(arr, target);
    cout << "\n"<<solution_2(arr, target);
    return 0;
}

Output

6
6