2824 Count Pairs Whose Sum is Less than Target
Problem Statement
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Approach
If we are sorting the input array we can get our Time complexity from O(N2) to O(log n). From there the solution is similar to Target Sum.
If the sum of the elements at left and right is less than the target value, it means all pairs with the current left element will also satisfy the condition. So, increment the count by right - left and shift the left pointer to the right.
Solution
var countPairs = function(nums, target) {
nums.sort((a,b) => a - b)
let l = 0,
r = nums.length - 1,
count = 0
while (l < r) {
if (nums[l] + nums[r] < target) {
count += (r - l)
l++
} else {
r--
}
}
return count
};