# Count the Number of Fair Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-fair-pairs)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-fair-pairs
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
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`

# Approaches
## Brute Force
This approach involves checking every possible pair of indices `(i, j)` where `i < j`. For each pair, we calculate the sum of the corresponding elements and check if it falls within the given `[lower, upper]` range.
**Time:** O(n^2), where n is the number of elements in `nums`. We iterate through all possible pairs, which is n * (n-1) / 2. · **Space:** O(1) extra space, as we only use a few variables to store the count and loop indices.
**Pros:** Simple to understand and implement.; Requires no modification of the input array.
**Cons:** Highly inefficient for large input sizes.; Will cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We iterate through all possible unique pairs of elements in the array, calculate their sum, and check if the sum is 'fair'.

- We initialize a counter for fair pairs to zero.
- We use two nested loops to generate all unique pairs `(i, j)` with `i < j`. The outer loop runs from `i = 0` to `n-2`, and the inner loop runs from `j = i+1` to `n-1`.
- Inside the inner loop, we compute the sum `(long) nums[i] + nums[j]` to avoid potential integer overflow.
- We then check if `lower <= sum <= upper`.
- If the condition is met, we increment our counter.
- After iterating through all pairs, the counter holds the total number of fair pairs.

```java
class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long sum = (long) nums[i] + nums[j];
                if (sum >= lower && sum <= upper) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use a nested loop. The outer loop iterates `i` from `0` to `n-2`.
3. The inner loop iterates `j` from `i+1` to `n-1`.
4. Inside the inner loop, calculate `sum = nums[i] + nums[j]`.
5. Check if `lower <= sum <= upper`.
6. If the condition is true, increment `count`.
7. After the loops complete, return `count`.

## Sorting with Binary Search
A more efficient approach is to first sort the array. Then, for each element `nums[i]`, we can use binary search to find how many other elements `nums[j]` (with `j > i`) satisfy the condition `lower <= nums[i] + nums[j] <= upper`. This condition can be rewritten as `lower - nums[i] <= nums[j] <= upper - nums[i]`.
**Time:** O(n log n). Sorting takes O(n log n). The main loop runs `n` times, and each iteration performs two binary searches, each taking O(log n). The total time is O(n log n + n * log n) = O(n log n). · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used. Java's `Arrays.sort` for primitives has an average space complexity of O(log n).
**Pros:** Significantly more efficient than brute force.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** More complex to implement than brute force.; Modifies the input array by sorting it. A copy must be made if the original order is needed.; While efficient, it's slightly slower than the two-pointer approach due to repeated binary searches.
### Explanation
By sorting the array, we can leverage binary search to speed up the process of finding valid partners for each element. For each `nums[i]`, we are looking for `nums[j]` in the remainder of the sorted array.

- First, we sort the input array `nums`.
- We iterate through the array with an index `i`.
- For each `nums[i]`, we define `min_val = lower - nums[i]` and `max_val = upper - nums[i]`.
- We then need to count elements in `nums` from index `i+1` to `n-1` that are in the range `[min_val, max_val]`.
- We can find this count by performing two binary searches:
    - Find the index of the first element `>= min_val` (the lower bound).
    - Find the index of the first element `> max_val` (the upper bound).
- The difference between these two indices gives the number of valid `j`'s for the current `i`.
- We sum these counts for all `i` to get the total.

```java
import java.util.Arrays;

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int start = findLowerBound(nums, i + 1, (long) lower - nums[i]);
            int end = findUpperBound(nums, i + 1, (long) upper - nums[i]);
            count += (end - start);
        }
        return count;
    }

    // Finds the first index `j` in nums[left...] such that nums[j] >= target
    private int findLowerBound(int[] nums, int left, long target) {
        int right = nums.length - 1;
        int result = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    // Finds the first index `j` in nums[left...] such that nums[j] > target
    private int findUpperBound(int[] nums, int left, long target) {
        int right = nums.length - 1;
        int result = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Initialize a `count` of fair pairs to 0.
3. Iterate through the array with an index `i` from `0` to `n-1`.
4. For each `nums[i]`, determine the required range for `nums[j]` as `[lower - nums[i], upper - nums[i]]`.
5. Use binary search on the subarray `nums[i+1...n-1]` to find the number of elements `nums[j]` that fall into this range.
6. This can be done by finding the index of the first element `>= (lower - nums[i])` (let's call it `start`) and the index of the first element `> (upper - nums[i])` (let's call it `end`).
7. The number of valid `j`'s for the current `i` is `end - start`.
8. Add this number to the total `count`.
9. Return `count` after the loop finishes.

## Sorting with Two Pointers
This is the most optimal approach. The core idea is to reframe the problem. Instead of directly counting pairs in the range `[lower, upper]`, we can calculate the number of pairs whose sum is less than or equal to a certain value `K`. The number of fair pairs is then `(pairs with sum <= upper) - (pairs with sum <= lower - 1)`. This subproblem can be solved efficiently in linear time on a sorted array using a two-pointer technique.
**Time:** O(n log n). Sorting the array takes O(n log n). Each call to the `countLessEqual` helper function takes O(n) time because the two pointers traverse the array at most once. The total time complexity is dominated by the sort, resulting in O(n log n). · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used. This is the same as the binary search approach.
**Pros:** The most efficient solution.; The two-pointer scan is O(n), which is faster than the O(n log n) scan of the binary search approach.; The logic is clean and the helper function is reusable.
**Cons:** Requires sorting, which alters the input array.; The logic of breaking the problem into `count(<=upper) - count(<=lower-1)` might be less intuitive at first.
### Explanation
This approach refines the sorting idea by using a more efficient two-pointer technique instead of repeated binary searches. The key insight is that the number of pairs `(i, j)` satisfying `lower <= sum <= upper` is equal to `(number of pairs with sum <= upper) - (number of pairs with sum < lower)`.

We can write a helper function `countLessEqual(K)` that efficiently counts pairs with a sum less than or equal to `K` on a sorted array.

- **`countLessEqual(K)` function:**
  - Initialize two pointers, `left` at the start of the array and `right` at the end.
  - While `left < right`:
    - If `nums[left] + nums[right] <= K`, we have found a valid pair. Since the array is sorted, `nums[left]` can also be paired with any element between `left+1` and `right`, and the sum will also be `<= K`. There are `right - left` such pairs. We add this to our count and move `left` one step to the right to consider the next element.
    - If `nums[left] + nums[right] > K`, the sum is too large. To reduce the sum, we must move the `right` pointer one step to the left.
- **Main Logic:**
  - First, sort the `nums` array.
  - The total number of fair pairs is `countLessEqual(upper) - countLessEqual(lower - 1)`.

```java
import java.util.Arrays;

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        return countLessEqual(nums, upper) - countLessEqual(nums, lower - 1);
    }

    private long countLessEqual(int[] nums, int val) {
        long count = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            if ((long) nums[left] + nums[right] <= val) {
                // If nums[left] + nums[right] <= val, then for this left pointer,
                // all pairs (left, j) where left < j <= right are valid.
                // There are (right - left) such pairs.
                count += (right - left);
                left++;
            } else {
                // Sum is too large, need to decrease it by moving the right pointer.
                right--;
            }
        }
        return count;
    }
}
```
### Algorithm
1. Define a helper function `countLessEqual(K)` that counts pairs `(i, j)` with `i < j` and `nums[i] + nums[j] <= K`.
2. Inside `countLessEqual(K)`:
   a. Use two pointers, `left = 0` and `right = n-1`.
   b. While `left < right`:
      i. If `nums[left] + nums[right] <= K`, it means `nums[left]` can form a valid pair with `nums[left+1], ..., nums[right]`. Add `right - left` to the count and increment `left`.
      ii. Otherwise, the sum is too large, so decrement `right`.
   c. Return the total count.
3. In the main function, first sort the `nums` array.
4. The final result is `countLessEqual(upper) - countLessEqual(lower - 1)`.

# Solutions
### Java

```java
class Solution {
public
  long countFairPairs(int[] nums, int lower, int upper) {
    Arrays.sort(nums);
    long ans = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      int j = search(nums, lower - nums[i], i + 1);
      int k = search(nums, upper - nums[i] + 1, i + 1);
      ans += k - j;
    }
    return ans;
  }
private
  int search(int[] nums, int x, int left) {
    int right = nums.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countFairPairs(vector<int> &nums, int lower, int upper) {
    long long ans = 0;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
      auto j = lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
      auto k =
          lower_bound(nums.begin() + i + 1, nums.end(), upper - nums[i] + 1);
      ans += k - j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int: nums . sort() ans = 0 for i, x in enumerate(nums): j = bisect_left(nums, lower - x, lo=i + 1) k = bisect_left(nums, upper - x + 1, lo=i + 1) ans += k - j return ans

```