Count the Number of Fair Pairs

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

For example, if nums = [0,1,7,4,4,5], lower = 3, and upper = 6, the output should be 6 because there are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

If nums = [1,7,9,2,5], lower = 11, and upper = 11, the output should be 1 because there is a single fair pair: (2,3).

Write an efficient algorithm to solve this problem. Consider the time and space complexity of your solution. Also, discuss potential edge cases and how to handle them. What are the Big O run-time and space usage? Why?

# Fair Pairs

## Problem Description

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).

## Naive Solution

The brute-force approach involves iterating through all possible pairs `(i, j)` where `i < j` and checking if the sum `nums[i] + nums[j]` falls within the range `[lower, upper]`.  This is straightforward to implement but inefficient.

```python
def count_fair_pairs_naive(nums, lower, upper):
    n = len(nums)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if lower <= nums[i] + nums[j] <= upper:
                count += 1
    return count

Optimal Solution

The optimal solution utilizes sorting and binary search to achieve a better time complexity. Here's the breakdown:

1. Sort the array: Sorting allows us to use binary search to efficiently find the range of values that, when added to nums[i], fall within the [lower, upper] range.
2. Iterate and Binary Search: For each element nums[i], we need to find the number of elements nums[j] (where j > i) such that lower <= nums[i] + nums[j] <= upper. This can be rewritten as lower - nums[i] <= nums[j] <= upper - nums[i]. We use binary search to find the first element greater than or equal to lower - nums[i] and the first element greater than upper - nums[i]. The difference between these two indices gives us the number of valid nums[j] values.

def count_fair_pairs_optimal(nums, lower, upper):
    nums.sort()
    n = len(nums)
    count = 0

    for i in range(n):
        left = lower - nums[i]
        right = upper - nums[i]

        left_index = find_first_greater_or_equal(nums, i + 1, left)
        right_index = find_first_greater(nums, i + 1, right)

        if left_index != -1 and right_index != -1:
             count += right_index - left_index

    return count

def find_first_greater_or_equal(nums, start, target):
    left = start
    right = len(nums) - 1
    index = -1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            index = mid
            right = mid - 1
        else:
            left = mid + 1
    return index


def find_first_greater(nums, start, target):
    left = start
    right = len(nums) - 1
    index = -1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] > target:
            index = mid
            right = mid - 1
        else:
            left = mid + 1
    return index

Big(O) Time Complexity Analysis

• Naive Solution: O(n^2), where n is the length of the array. This is because we have nested loops iterating through all possible pairs.
• Optimal Solution: O(n log n), where n is the length of the array. The dominant operations are:
  • Sorting: O(n log n)
  • Iteration through the array: O(n)
  • Binary search within the loop: O(log n) for each iteration. Therefore, the overall time complexity is O(n log n + n log n) which simplifies to O(n log n).

Big(O) Space Complexity Analysis

• Naive Solution: O(1). The naive solution uses a constant amount of extra space.
• Optimal Solution: O(1). The space complexity of the optimal solution depends on the sorting algorithm used. If an in-place sorting algorithm like heapsort or quicksort is used, the space complexity is O(1). If merge sort were used, it would be O(n).

Edge Cases

1. Empty Array: If the input array is empty, there are no fair pairs, so the function should return 0.
2. Array with One Element: If the array has only one element, there are no possible pairs, so return 0.
3. lower > upper: Although the constraints specify lower <= upper, it's good to consider this case. If lower > upper, there can be no fair pairs, so the function should return 0.
4. Duplicate Numbers: The algorithm should correctly handle duplicate numbers in the array.
5. Large Input Array: The algorithm should be efficient enough to handle large input arrays (up to 10^5 elements).

def count_fair_pairs(nums, lower, upper):
    if not nums or len(nums) < 2:
        return 0

    if lower > upper:
        return 0

    return count_fair_pairs_optimal(nums, lower, upper)