2563. Count the Number of Fair Pairs

Description

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

• 0 <= i < j < n, and
• lower <= nums[i] + nums[j] <= upper

 

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).

 

Constraints:

• 1 <= nums.length <= 105
• nums.length == n
•  <= nums[i] <= 109

 

Solutions

Solution: Two Pointers

• Time complexity: O(nlogn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
const countFairPairs = function (nums, lower, upper) {
  const n = nums.length;

  nums.sort((a, b) => a - b);

  const getPairCount = target => {
    let left = 0;
    let right = n - 1;
    let result = 0;

    while (left < right) {
      const sum = nums[left] + nums[right];

      if (sum <= target) {
        result += right - left;
        left += 1;
      } else {
        right -= 1;
      }
    }
    return result;
  };

  return getPairCount(upper) - getPairCount(lower - 1);
};