Count the Number of Fair Pairs

MEDIUM

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

Constraints:

1 <= nums.length <= 10⁵
nums.length == n
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= lower <= upper <= 10⁹

Approaches

Checkout 3 different approaches to solve Count the Number of Fair Pairs. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Initialize a counter count to 0.
Use a nested loop. The outer loop iterates i from 0 to n-2.
The inner loop iterates j from i+1 to n-1.
Inside the inner loop, calculate sum = nums[i] + nums[j].
Check if lower <= sum <= upper.
If the condition is true, increment count.
After the loops complete, return count.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1) extra space, as we only use a few variables to store the count and loop indices.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count the Number of Fair Pairs. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Count the Number of Fair Pairs

Algorithms:

Binary SearchSorting

Patterns:

Two Pointers

Data Structures:

Array

Companies:

Qualcomm |Salesforce |