Count the number of fair pairs

Array Two Pointers Binary Search Sorting

52.7% acceptance

Feb 25, 2026

2007

150

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

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_fair_pairs(mut nums: Vec<i32>, lower: i32, upper: i32) -> i64 {
    nums.sort_unstable();
    let n = nums.len();
    let mut count = 0i64;
    // For each i, count j > i with lower <= nums[i]+nums[j] <= upper
    // Binary search in nums[i+1..n] for range [lower-nums[i], upper-nums[i]]
    for i in 0..n - 1 {
      let lo = lower as i64 - nums[i] as i64;
      let hi = upper as i64 - nums[i] as i64;
      let left = nums[i + 1..].partition_point(|&x| (x as i64) < lo);
      let right = nums[i + 1..].partition_point(|&x| (x as i64) <= hi);
      count += (right - left) as i64;
    }
    count
  }
}