Leetcode problem 90 - Count Pairs Whose Sum is Less than Target

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.

Example 1:

Input: nums = [-1,1,2,3,1], target = 2 Output: 3 Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:

• (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
• (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
• (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target. Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2 Output: 10 Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:

• (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
• (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
• (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
• (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
• (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
• (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
• (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
• (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
• (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
• (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target

Constraints:

1 <= nums.length == n <= 50 -50 <= nums[i], target <= 50

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var countPairs = function (nums, target) {
  // Sort the array in ascending order
  nums.sort((a, b) => a - b);

  // Initialize variables for counting, left pointer, and right pointer
  let count = 0; // Counter for pairs that sum to less than the target
  let left = 0; // Left pointer starting from the beginning of the sorted array
  let right = nums.length - 1; // Right pointer starting from the end of the sorted array

  // Iterate while the left pointer is less than the right pointer
  while (left < right) {
    // Check if the sum of elements at left and right pointers is less than the target
    if (nums[left] + nums[right] < target) {
      // Increment the count by the number of pairs between the left and right pointers
      count += right - left;
      // Move the left pointer to the next element
      left++;
    } else {
      // If the sum is greater or equal to the target, move the right pointer to the previous element
      right--;
    }
  }

  // Return the final count of pairs that sum to less than the target
  return count;
};

/**
let count = 0;
    for(let i = 0; i < nums.length; i++){
        for(let j = i + 1; j < nums.length; j++){
            if(nums[i] + nums[j] < target){
                count++
            }
        }
    }
    return count
 */

The time complexity of this solution is O(n log n) due to the sorting of the array.

The space complexity is constant O(1) for the entire algorithm since the sorting is considered in-place and doesn’t use additional space proportional to the input size.