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


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.


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)
		} else {

	return count




Two Pointers