Parottasalna

Problem Statement

Geeks For Geeks : https://www.geeksforgeeks.org/problems/count-pairs-whose-sum-is-less-than-target/1

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.

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).

My Approach

Sorted the array and used two pointer approach to find the possible pairs.

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