Count the Number of Fair Pairs

Medium
1361.

Count the Number of Fair Pairs

Count the Number of Fair Pairs is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.

Given an integer array nums of length n and two integers lower and upper, count the fair pairs.

A pair of indices (i, j) is fair when 0 <= i < j < n and lower <= nums[i] + nums[j] <= upper.

CodeKairo note: the original allows n up to 10^5 and returns a 64-bit count; here n <= 5 * 10^4, so the answer fits in a 32-bit integer. A single pair sum can still reach 2 * 10^9.

Example 1

Input
nums = [2,-1,5,3,0], lower = 2, upper = 5
Output
6
Explanation
The pairs with sums 5 (2+3), 2 (2+0), 4 (-1+5), 2 (-1+3), 5 (5+0) and 3 (3+0).

Example 2

Input
nums = [4,6,1,9], lower = 10, upper = 10
Output
2
Explanation
4 + 6 and 1 + 9.

Example 3

Input
nums = [7], lower = 0, upper = 100
Output
0
Explanation
A single element forms no pair.

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= lower <= upper <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countFairPairs = function(nums, lower, upper) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Number of Fair Pairs — Problem & Solution

Count the Number of Fair Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count the Number of Fair Pairs is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given an integer array nums of length n and two integers lower and upper, count the fair pairs.

A pair of indices (i, j) is fair when 0 <= i < j < n and lower <= nums[i] + nums[j] <= upper.

CodeKairo note: the original allows n up to 10^5 and returns a 64-bit count; here n <= 5 * 10^4, so the answer fits in a 32-bit integer. A single pair sum can still reach 2 * 10^9.

Example 1

Input: nums = [2,-1,5,3,0], lower = 2, upper = 5
Output: 6
Explanation: The pairs with sums 5 (2+3), 2 (2+0), 4 (-1+5), 2 (-1+3), 5 (5+0) and 3 (3+0).

Example 2

Input: nums = [4,6,1,9], lower = 10, upper = 10
Output: 2
Explanation: 4 + 6 and 1 + 9.

Example 3

Input: nums = [7], lower = 0, upper = 100
Output: 0
Explanation: A single element forms no pair.

Constraints

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

Hints for Count the Number of Fair Pairs

  1. Hint 1

    The count of pairs does not depend on the order of the array — only on which values exist. So you may sort it.

  2. Hint 2

    Counting pairs with a sum inside [lower, upper] is (pairs with sum <= upper) minus (pairs with sum <= lower - 1).

  3. Hint 3

    In a sorted array, count pairs with sum <= x with two pointers: if a[i] + a[j] <= x, all of a[i+1..j] pair with a[i], so add j - i and move i right; otherwise move j left.

How to solve Count the Number of Fair Pairs

Sorting does not change the set of unordered pairs, and on a sorted array "how many pairs sum to at most x" is a linear two-pointer count. The range answer is the difference of two such counts.

Approach

  1. Sort a copy of nums ascending.
  2. Define atMost(x): with i = 0, j = n - 1, while i < j: if a[i] + a[j] <= x, add j - i (every partner of a[i] in i+1..j) and increment i; otherwise decrement j.
  3. Return atMost(upper) - atMost(lower - 1).

Why it works

If a[i] + a[j] <= x, then a[i] + a[t] <= x for every t in (i, j] because the array is sorted, so all j - i pairs are counted at once and a[i] is finished. If the sum is too big, a[j] exceeds the limit with every remaining partner (all of them are >= a[i]), so a[j] is finished. Each step finishes one element, so each pair is classified exactly once.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Pair sums reach ±2·10^9, beyond 32-bit range — add in 64-bit.
  • Count unordered pairs i < j: never pair an element with itself.
  • Binary search per element (lower/upper bound in the suffix) also works in O(n log n); the two-pointer version avoids off-by-one errors with the bounds.

Reference solution

Python

from typing import List

def countFairPairs(nums: List[int], lower: int, upper: int) -> int:
    a = sorted(nums)

    def at_most(limit: int) -> int:
        i = 0
        j = len(a) - 1
        cnt = 0
        while i < j:
            if a[i] + a[j] <= limit:
                cnt += j - i
                i += 1
            else:
                j -= 1
        return cnt

    return at_most(upper) - at_most(lower - 1)

Java

static long fairAtMost2563(int[] a, long limit) {
    int i = 0, j = a.length - 1;
    long cnt = 0;
    while (i < j) {
        if ((long) a[i] + a[j] <= limit) { cnt += j - i; i++; }
        else j--;
    }
    return cnt;
}

public static int countFairPairs(int[] nums, int lower, int upper) {
    int[] a = nums.clone();
    Arrays.sort(a);
    return (int) (fairAtMost2563(a, upper) - fairAtMost2563(a, (long) lower - 1));
}

C++

long long fairAtMost2563(const vector<int>& a, long long limit) {
    int i = 0, j = (int) a.size() - 1;
    long long cnt = 0;
    while (i < j) {
        if ((long long) a[i] + a[j] <= limit) { cnt += j - i; i++; }
        else j--;
    }
    return cnt;
}

int countFairPairs(vector<int>& nums, int lower, int upper) {
    vector<int> a(nums.begin(), nums.end());
    sort(a.begin(), a.end());
    return (int) (fairAtMost2563(a, upper) - fairAtMost2563(a, (long long) lower - 1));
}

JavaScript

var countFairPairs = function(nums, lower, upper) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var atMost = function(limit) {
        var i = 0, j = a.length - 1, cnt = 0;
        while (i < j) {
            if (a[i] + a[j] <= limit) { cnt += j - i; i++; }
            else j--;
        }
        return cnt;
    };
    return atMost(upper) - atMost(lower - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms