Count Pairs Whose Sum is Less than Target
Problem
Given an array nums and an integer target, return the number of index pairs (i, j) with i < j and nums[i] + nums[j] < target.
nums = [-1,1,2,3,1], target = 23def count_pairs(nums, target):
nums.sort()
lo, hi, count = 0, len(nums) - 1, 0
while lo < hi:
if nums[lo] + nums[hi] < target:
count += hi - lo
lo += 1
else:
hi -= 1
return countfunction countPairs(nums, target) {
nums.sort((a, b) => a - b);
let lo = 0, hi = nums.length - 1, count = 0;
while (lo < hi) {
if (nums[lo] + nums[hi] < target) { count += hi - lo; lo++; }
else hi--;
}
return count;
}class Solution {
public int countPairs(List<Integer> nums, int target) {
Collections.sort(nums);
int lo = 0, hi = nums.size() - 1, count = 0;
while (lo < hi) {
if (nums.get(lo) + nums.get(hi) < target) { count += hi - lo; lo++; }
else hi--;
}
return count;
}
}int countPairs(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int lo = 0, hi = nums.size() - 1, count = 0;
while (lo < hi) {
if (nums[lo] + nums[hi] < target) { count += hi - lo; lo++; }
else hi--;
}
return count;
}Explanation
The pairs are counted by value, not position, and reordering the array does not change how many pairs sum below the target. So we begin by sorting the array, which unlocks a fast two-pointer sweep.
We place lo at the start and hi at the end. If nums[lo] + nums[hi] < target, then because the array is sorted, nums[lo] paired with every element between lo and hi is also below target — that is hi - lo pairs all at once. We add them and move lo right.
If the sum is too big, the only way to shrink it is to drop the largest element, so we move hi left. Either way one pointer moves each step, so the loop runs in linear time after the sort.
This counts each valid pair exactly once because we always fix the smaller index as lo and never revisit a position once a pointer passes it.
Example: sorted [-1,1,1,2,3], target = 2. With lo=-1, hi=3: sum 2 not < 2 → move hi. Then -1 + 2 = 1 < 2 → add hi-lo = 3 pairs, move lo. Then 1 + 2 = 3 ≥ 2 → move hi until pointers cross. Total 3.