Skip to content

← leetcode

Count the Number of Fair Pairs

· Medium

LeetCode problem 2563

For this question, you can simplify it to:

what is the number of pairs that are smaller than equal to upper minus the number of pairs that are smaller than lower.

To accomplish this, we can create a two-pointers function that calculates the number of pairs that are smaller than equal to target.

In this function, we have 2 pointers; l points to the beginning of nums, while r points to the end of nums, and an ans variable to track the . Now, while l < r,

  • if nums[l] + nums[r] <= target,
    • then we can simply add r-l to ans
    • and increment l to increase nums[l] + nums[r]
  • if nums[l] + nums[r] > target,
    • then we can simply decrement r to decrease nums[l] + nums[r]

code

class Solution {
public:
    long long lessThanTarget(vector<int>& nums, int target) {
        long long l = 0, r = nums.size()-1, ans = 0;
        while (l < r) {
            if (nums[l] + nums[r] <= target) {
                ans += r-l;
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return lessThanTarget(nums, upper) - lessThanTarget(nums, lower-1);
    }
};

complexity

  • Time: O(n log(n)) where n is the size of nums
  • Space: O(1)

learnings

  • stop forgetting that to find the values between l and r, you can simply find the values smaller than r and subtract from it the number of values smaller than l