Scale Engineer

Count the Number of Fair Pairs

Med
#2343Time: 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.2 companies
Patterns
Two Pointers
Algorithms
Binary SearchSorting
Data structures
Array
Companies
QualcommSalesforce

Prompt

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

3 approaches with complexity analysis and trade-offs.

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

  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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem