2563. Count the Number of Fair Pairs

Problem

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

• -109&nbsp;<= nums[i] <= 109

• -109&nbsp;<= lower <= upper <= 109

Solution (Java)

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result + binarySearch1(nums, nums[i], i, lower, upper) - binarySearch2(nums, nums[i], i, lower, upper);
        }
        return result;
    }
    public long binarySearch1(int[] nums, int currentValue, int index, int lower, int upper) {
        int start = index + 1;
        int end = nums.length;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > (upper - currentValue)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    public long binarySearch2(int[] nums, int currentValue, int index, int lower, int upper) {
        int start = index + 1;
        int end = nums.length;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < (lower - currentValue)) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).