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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Fair Pairs

Number: 2699

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, Amazon, Salesforce

Problem Description

Given a 0-indexed integer array nums and two integers lower and upper, count the number of fair pairs (i, j) such that 0 <= i < j < nums.length and lower <= nums[i] + nums[j] <= upper.

Key Insights

  • Sorting the array simplifies searching for pairs with required sum limits.
  • For each element, binary search is used to locate:
    • The first index where the complement makes the sum >= lower.
    • The last index where the complement makes the sum <= upper.
  • This avoids the need for a nested loop through the entire array, yielding a more efficient solution.

Space and Time Complexity

Time Complexity: O(n log n), primarily due to sorting and (for each element) binary search operations. Space Complexity: O(n) if sorting creates a copy; O(1) additional space if sorting in-place.

Solution

The solution starts by sorting the input array. For each element at index i in the sorted array, we search for indices j (where j > i) such that the sum of nums[i] and nums[j] falls between lower and upper.
Two binary search operations are performed:

  1. To find the smallest index j where nums[i] + nums[j] >= lower.
  2. To find the largest index j where nums[i] + nums[j] <= upper. Subtracting the two positions (and summing the counts for each i) gives the total number of fair pairs.
    Edge cases (like no valid pair) are automatically handled by the binary search approach.

Code Solutions

import bisect

def countFairPairs(nums, lower, upper):
    # Sort the array to allow binary search
    nums.sort()
    fair_pairs = 0
    n = len(nums)
    
    for i in range(n):
        # Find lower bound index for the required complement so that nums[i] + nums[j] >= lower
        left = bisect.bisect_left(nums, lower - nums[i], i + 1, n)
        # Find upper bound index for the required complement so that nums[i] + nums[j] <= upper
        right = bisect.bisect_right(nums, upper - nums[i], i + 1, n)
        fair_pairs += (right - left)
    
    return fair_pairs

# Example usage:
print(countFairPairs([0,1,7,4,4,5], 3, 6))  # Expected output: 6
← Back to All Questions