We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Fair Pairs

Difficulty: Medium

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

Key Insights

  • We need to count pairs of indices such that their sum falls within a specified range.
  • The brute force approach of checking all pairs would be inefficient for large arrays (O(n^2)).
  • Sorting the array can help us use a two-pointer technique or binary search to efficiently find valid pairs.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array. Space Complexity: O(1) - if we sort in place, or O(n) if we use additional space for sorting.

Solution

To efficiently count the number of fair pairs, follow these steps:

  1. Sort the nums array.
  2. Use a two-pointer approach. For each element nums[i], determine the valid range of nums[j] that satisfies the sum condition with nums[i].
  3. For each nums[i], use binary search to find the lower and upper bounds of valid indices for j.
  4. Count how many j indices are valid for each i and accumulate the counts.

This approach leverages sorting and efficient range queries to minimize the number of operations needed to find valid pairs.

Code Solutions

def count_fair_pairs(nums, lower, upper):
    nums.sort()  # Sort the array
    n = len(nums)
    count = 0

    for i in range(n):
        # Find the range of j using binary search
        left = bisect.bisect_left(nums, lower - nums[i], i + 1)
        right = bisect.bisect_right(nums, upper - nums[i], i + 1)
        count += right - left  # Count valid j's

    return count
← Back to All Questions