Count the Number of Fair Pairs

Count the Number of Fair Pairs

What is this problem about?

The Count the Number of Fair Pairs coding problem provides an array of integers and two thresholds: lower and upper. A pair of indices $(i, j)$ is considered "fair" if $i < j$ and the sum of the elements at these indices falls within the range $[lower, upper]$.

Your task is to return the total count of such unique pairs.

Why is this asked in interviews?

This is a high-signal problem for companies like Microsoft, Qualcomm, and Meta. It tests a candidate's ability to optimize a search from $O(N^2)$ to $O(N \log N)$. It evaluates proficiency with the sorting interview pattern and the two pointers interview pattern (specifically the "sliding window" version for sums). It’s also an excellent test of whether you can decompose a "range count" problem into two "upper bound count" problems.

Algorithmic pattern used

This problem is solved using Sorting and Two Pointers.

1. Sort the array: Since the order of indices $(i, j)$ doesn't actually matter for the sum (only that they are distinct), sorting allows us to use pointers.
2. Decompose the condition: Finding pairs in $[lower, upper]$ is equivalent to countPairsWithSum(upper) - countPairsWithSum(lower - 1).
3. Pointers Logic: To count pairs with sum <= target, initialize left = 0 and right = n - 1. If nums[left] + nums[right] <= target, then all pairs between left and right (e.g., (left, left+1), ..., (left, right)) are valid. Increment count by right - left and move left. Otherwise, move right.

Example explanation

nums = [3, 1, 4, 2], lower = 4, upper = 5

1. Sort nums: [1, 2, 3, 4].
2. Count pairs $\le 5$:
   • L=0(1), R=3(4): $1+4 \le 5$. Count += 3. L=1.
   • L=1(2), R=3(4): $2+4 > 5$. R=2.
   • L=1(2), R=2(3): $2+3 \le 5$. Count += 1. L=2.
   • Total $\le 5$ is 4 pairs.
3. Count pairs $\le 3$:
   • L=0(1), R=3(4): $1+4 > 3$. R=2.
   • L=0(1), R=2(3): $1+3 > 3$. R=1.
   • L=0(1), R=1(2): $1+2 \le 3$. Count += 1. L=1.
   • Total $\le 3$ is 1 pair.
4. Result: $4 - 1 = 3$.

Common mistakes candidates make

• Brute Force: Using nested loops ($O(N^2)$), which times out for large inputs.
• Off-by-one errors: Incorrectly using countPairsWithSum(lower) instead of countPairsWithSum(lower - 1).
• Double counting: Counting $(i, j)$ and $(j, i)$ separately.

Interview preparation tip

Whenever you need to count items in a range $[A, B]$, always ask yourself if calculating f(B) - f(A-1) is easier. This "prefix property" applies to array sums, frequency counts, and pair sums alike.