Two Pointers - Count Pairs Whose Sum is Less Than Target

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.

Input: nums=[-1,1,2,3,1], target=2 → Output: 3

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

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

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)