Count Pairs whose sum is less than target

Problem Statement:

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⁴

Code Implementation:

class Solution:
    #Complete the below function
    def countPairs(self, arr, target):
        #Your code here
        arr.sort()
        left, right = 0, len(arr) - 1
        count = 0
        while left < right:
            if arr[left] + arr[right] < target:
                count += right - left
                left += 1
            else:
                right -= 1
        return count

Input Examples and Output:

Example 1:

Input:

Output:

Explanation: The valid pairs are:

• $(2,2)$
• $(2,1)$
• $(3,1)$
• $(2,1)$

Example 2:

Input:

Output:

Explanation: The valid pairs are:

• $(2,1)$
• $(2,3)$
• $(2,4)$
• $(1,3)$
• $(1,4)$
• $(1,5)$

Explanation (Line-by-Line):

Code:

Explanation:

• Sorting the array helps in efficiently finding pairs using the two-pointer technique. After sorting, elements are in ascending order.

Code:

Explanation:

• left is initialized to point to the smallest element in the array.
• right is initialized to point to the largest element in the array.
• count keeps track of the total number of pairs found.

Code:

Explanation:

• The loop runs until the two pointers meet. At this point, all possible pairs are checked.

Code:

Explanation:

• The sum of the elements at left and right pointers is checked.
• If the sum is less than the target, all pairs from left to right are valid (since the array is sorted, all elements between left and right will also satisfy the condition).

Code:

Explanation:

• Add all pairs from left to right to the count. There are exactly $(\text{right}-\text{left})$ pairs.

Code:

Explanation:

• Move the left pointer to the next element to check for the next possible pairs.

Code:

Explanation:

• If the sum of arr[left] + arr[right] is greater than or equal to the target, move the right pointer inward to reduce the sum.

Code:

Explanation:

• Return the total count of valid pairs found.

Complexity Analysis:

1. Time Complexity:
   • Sorting: $O(n\log n)$
   • Two-pointer traversal: $O(n)$
   • Total: $O(n\log n)$
2. Space Complexity:
   • $O(1)$: Sorting is done in-place, and no extra space is used apart from variables.