Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2563.html

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
  • -109 <= nums[i] <= 109
  • -109 <= lower <= upper <= 109

Solutions

Solution 1: Sorting + Binary Search

First, we sort the array nums in ascending order. Then, for each nums[i], we use binary search to find the lower bound j of nums[j], i.e., the first index that satisfies nums[j] >= lower - nums[i]. Then, we use binary search again to find the lower bound k of nums[k], i.e., the first index that satisfies nums[k] >= upper - nums[i] + 1. Therefore, [j, k) is the index range for nums[j] that satisfies lower <= nums[i] + nums[j] <= upper. The count of these indices corresponding to nums[j] is k - j, and we can add this to the answer. Note that $j > i$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the length of the array nums.

  • class Solution {
        public long countFairPairs(int[] nums, int lower, int upper) {
            Arrays.sort(nums);
            long ans = 0;
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                int j = search(nums, lower - nums[i], i + 1);
                int k = search(nums, upper - nums[i] + 1, i + 1);
                ans += k - j;
            }
            return ans;
        }
    
        private int search(int[] nums, int x, int left) {
            int right = nums.length;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (nums[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
    
  • class Solution {
    public:
        long long countFairPairs(vector<int>& nums, int lower, int upper) {
            long long ans = 0;
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size(); ++i) {
                auto j = lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
                auto k = lower_bound(nums.begin() + i + 1, nums.end(), upper - nums[i] + 1);
                ans += k - j;
            }
            return ans;
        }
    };
    
  • class Solution:
        def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
            nums.sort()
            ans = 0
            for i, x in enumerate(nums):
                j = bisect_left(nums, lower - x, lo=i + 1)
                k = bisect_left(nums, upper - x + 1, lo=i + 1)
                ans += k - j
            return ans
    
    
  • func countFairPairs(nums []int, lower int, upper int) (ans int64) {
    	sort.Ints(nums)
    	for i, x := range nums {
    		j := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= lower-x })
    		k := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= upper-x+1 })
    		ans += int64(k - j)
    	}
    	return
    }
    
  • function countFairPairs(nums: number[], lower: number, upper: number): number {
        const search = (x: number, l: number): number => {
            let r = nums.length;
            while (l < r) {
                const mid = (l + r) >> 1;
                if (nums[mid] >= x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        };
    
        nums.sort((a, b) => a - b);
        let ans = 0;
        for (let i = 0; i < nums.length; ++i) {
            const j = search(lower - nums[i], i + 1);
            const k = search(upper - nums[i] + 1, i + 1);
            ans += k - j;
        }
        return ans;
    }
    
    

All Problems

All Solutions