Count Pairs whose sum is less than target

Given an array arr[] and an integer target. You have to find the number of pairs in the array whose sum is strictly less than the target.

Examples:

Input: arr[] = [7, 2, 5, 3], target = 8
Output: 2
Explanation: There are 2 pairs with sum less than 8: (2, 5) and (2, 3). 

Input: arr[] = [5, 2, 3, 2, 4, 1], target = 5
Output: 4
Explanation: There are 4 pairs whose sum is less than 5: (2, 2), (2, 1), (3, 1) and (2, 1).

Input: arr[] = [2, 1, 8, 3, 4, 7, 6, 5], target = 7
Output: 6
Explanation: There are 6 pairs whose sum is less than 7: (2, 1), (2, 3), (2, 4), (1, 3), (1, 4) and (1, 5).

Constraints:
1 <= arr.size() <= 10⁵
0 <= arr[i] <= 10⁴
1 <= target <= 10⁴

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int countPairs(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());  // Sort the array
        int arrSize = arr.size();
        int leftPointer = 0, rightPointer = arrSize - 1; 
        int validPairsCount = 0, totalPairs = 0;

        // Traverse the array with two pointers
        while (leftPointer < rightPointer && leftPointer < arrSize && rightPointer >= 0) {
            if ((arr[leftPointer] + arr[rightPointer]) >= target) {
                rightPointer--;  // Decrease the right pointer if sum is large enough
            } else {
                validPairsCount = (rightPointer - leftPointer + 1);  // Calculate valid pairs
                totalPairs += (validPairsCount - 1);  // Add valid pairs to total count
                leftPointer++;  // Move the left pointer forward
            }
        }

        return totalPairs;
    }
};

class Solution:
    def countPairs(self, arr, target):
        arr.sort()  # Sort the array
        arrSize = len(arr)
        leftPointer = 0
        rightPointer = arrSize - 1
        validPairsCount = 0
        totalPairs = 0

        # Traverse the array with two pointers
        while leftPointer < rightPointer and leftPointer < arrSize and rightPointer >= 0:
            if (arr[leftPointer] + arr[rightPointer]) >= target:
                rightPointer -= 1  # Decrease the right pointer if sum is large enough
            else:
                validPairsCount = (rightPointer - leftPointer + 1)  # Calculate valid pairs
                totalPairs += (validPairsCount - 1)  # Add valid pairs to total count
                leftPointer += 1  # Move the left pointer forward

        return totalPairs

Time Complexity:

• Sorting the Array:

  The array is sorted at the beginning, which takes \( O(n \log n) \), where \( n \) is the size of the array.

• Two-Pointer Traversal:

  The two-pointer approach processes each element at most once, resulting in \( O(n) \).

• Overall Time Complexity:

  \( O(n \log n + n) = O(n \log n) \), as the sorting step dominates.

Space Complexity:

• Auxiliary Space:

  The sorting algorithm might use \( O(\log n) \) space if an in-place sorting algorithm (like quicksort) is used.

• Additional Data Structures:

  The algorithm uses a constant amount of space for variables like pointers and counters, contributing \( O(1) \).

• Overall Space Complexity:

  \( O(\log n) \) due to the sorting step.