Count Pairs whose sum is less than target

JavaView on GFG

Intuition

Count pairs with sum < target. Sort + two pointers.

Algorithm

1Sort. l=0, r=n-1. If nums[l]+nums[r] < target: count += r-l, l++. Else: r--.

Common Pitfalls

•When sum < target: all pairs with r fixed from l to r-1 also qualify. Count += r-l.

Count Pairs whose sum is less than target.java

Java

// Approach: Sort array. Two pointers: for each left pointer, binary search or move right pointer.
// Time: O(n log n) Space: O(1)
class Solution {
    int countPairs(int arr[], int target) {
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        int count = 0;
        Arrays.sort(arr);
        while (left < right) {
            if (arr[left] + arr[right] < target) {
                count += (right - left);
                left++;
            } else
                right--;
        }
        return count;
    }
}

Was this solution helpful?