NeetCode #293LC-2563MediumBinary Search
← Back to All Problems#293 · #2563 · Count the Number of Fair Pairs(统计公平数对的数目)
📌 Problem Statement & Constraints
Given a 0-indexed integer array
nums and two integers lower and upper, return the number of fair pairs: pairs (i, j) with i < j and lower <= nums[i] + nums[j] <= upper. Constraints: 1 <= nums.length <= 10^5, -10^9 <= nums[i], lower, upper <= 10^9.💡 Core Algorithmic Approaches
- Counting pairs within a range is the difference of two counts: pairs with sum at most
upperminus pairs with sum at mostlower - 1. - For a fixed limit, sort the array and use two pointers: if
nums[l] + nums[r] <= limit, then allr - lpairs with thisland anyjin(l, r]are valid. - Advance
lon success and decrementrotherwise. - This is O(n log n) overall, dominated by the sort.
💻 Benchmark Python3 Implementation
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
def count_at_most(limit: int) -> int:
l, r = 0, len(nums) - 1
res = 0
while l < r:
if nums[l] + nums[r] <= limit:
res += r - l # all pairs (l, l+1..r) qualify
l += 1
else:
r -= 1
return res
# inclusive range = at most upper minus at most (lower - 1)
return count_at_most(upper) - count_at_most(lower - 1)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort plus two linear scans.
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Using two pointers directly for the range: the range has two bounds, so the subtraction of two one-sided counts is the clean way.
- Using
count_at_most(lower): that excludes pairs summing exactly tolower; the subtraction useslower - 1. - Sorting inside
count_at_most: the sort happens once, outside. - Assuming values are positive: they can be negative, and the two-pointer logic is unaffected.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.