Show problems as
Classic problem #2563MediumArrayTwo PointersBinary SearchSorting

Count the Number of Fair Pairs

Real-world version: Pairs Whose Total Falls in Range
Tracked in this browser only
Read Count the Number of Fair Pairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Readings are given as nums, along with bounds lower and upper.

A pair of positions i before j is in range when nums[i] + nums[j] is at least lower and at most upper.

Return how many pairs are in range.

Examples

Example 1

Input
nums = [14, 3, 27, 9, 41], lower = 20, upper = 40
Output
3

Sorted, the readings run 3, 9, 14, 27, 41. The pairs totalling between 20 and 40 are 3 and 27, 9 and 27, 14 and 27, and 3 and 41... of those the last totals 44, so it does not count, leaving the three that do.

Example 2

Input
nums = [0, 0, 0, 0], lower = 0, upper = 0
Output
6

Every pair totals nothing, and there are six pairs among four readings.

Example 3

Input
nums = [1, 2, 3], lower = 100, upper = 200
Output
0

No pair totals anywhere near the range.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= lower <= upper <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_fair_pairs(nums: list[int], lower: int, upper: int) -> int:
Java
public long countFairPairs(int[] nums, int lower, int upper)

More on the same topics