2563. Count the Number of Fair Pairs LeetCode Solution

In this guide, you will get 2563. Count the Number of Fair Pairs LeetCode Solution with the best time and space complexity. The solution to Count the Number of Fair Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count the Number of Fair Pairs solution in C++
Count the Number of Fair Pairs solution in Java
Count the Number of Fair Pairs solution in Python
Additional Resources

2563. Count the Number of Fair Pairs LeetCode Solution image

Problem Statement of Count the Number of Fair Pairs

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

2563. Count the Number of Fair Pairs LeetCode Solution in C++

class Solution {
 public:
  long long countFairPairs(vector<int>& nums, int lower, int upper) {
    // nums[i] + nums[j] == nums[j] + nums[i], so the condition that i < j
    // degrades to i != j and we can sort the array.
    ranges::sort(nums);
    return countLess(nums, upper) - countLess(nums, lower - 1);
  }

 private:
  long countLess(const vector<int>& nums, int sum) {
    long res = 0;
    for (int i = 0, j = nums.size() - 1; i < j; ++i) {
      while (i < j && nums[i] + nums[j] > sum)
        --j;
      res += j - i;
    }
    return res;
  }
};
/* code provided by PROGIEZ */

2563. Count the Number of Fair Pairs LeetCode Solution in Java

class Solution {
  public long countFairPairs(int[] nums, int lower, int upper) {
    // nums[i] + nums[j] == nums[j] + nums[i], so the condition that i < j
    // degrades to i != j and we can sort the array.
    Arrays.sort(nums);
    return countLess(nums, upper) - countLess(nums, lower - 1);
  }

  private long countLess(int[] nums, int sum) {
    long res = 0;
    for (int i = 0, j = nums.length - 1; i < j; ++i) {
      while (i < j && nums[i] + nums[j] > sum)
        --j;
      res += j - i;
    }
    return res;
  }
}
// code provided by PROGIEZ

2563. Count the Number of Fair Pairs LeetCode Solution in Python

class Solution:
  def countFairPairs(self, nums: list[int], lower: int, upper: int) -> int:
    # nums[i] + nums[j] == nums[j] + nums[i], so the condition that i < j
    # degrades to i != j and we can sort the array.
    nums.sort()

    def countLess(summ: int) -> int:
      res = 0
      i = 0
      j = len(nums) - 1
      while i < j:
        while i < j and nums[i] + nums[j] > summ:
          j -= 1
        res += j - i
        i += 1
      return res

    return countLess(upper) - countLess(lower - 1)
 # code by PROGIEZ