Count Pairs Whose Sum is Less Than Target

Share

Given a list of integers nums and target, return the number of pairs (i, j) with i < j such that nums[i] + nums[j] < target.

Example 1
Input: nums=[-1,1,2,3,1], target=2 → Output: 3
Example 2
Input: nums=[-6,2,5,-2,-7,-1,3], target=-2 → Output: 10

Solution Approach

Sort the array. Use two pointers. If sum < target, all pairs (lo, lo+1..hi) are valid. Count them and advance lo.

  • Sort nums. lo=0, hi=n-1, count=0.
  • If nums[lo]+nums[hi] < target: count += hi-lo (all pairs with lo are valid), lo++.
  • Else: hi-- (sum too large).
Java
import java.util.Arrays;

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(arr);
        int lo = 0, hi = arr.length - 1, count = 0;
        while (lo < hi) {
            if (arr[lo] + arr[hi] < target) { count += hi - lo; lo++; }
            else hi--;
        }
        return count;
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(1)