POTD #16 - Count Pairs whose sum is less than target | Geeks For Geeks

{% raw %}

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 = 8Output: 2Explanation: There are 2 pairs with sum less than 8: (2, 5) and (2, 3). 

Input: arr[] = [5, 2, 3, 2, 4, 1], target = 5Output: 4Explanation: 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                    

{% endraw %}