⚡Flashcard Drill➔
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

  1. Counting pairs within a range is the difference of two counts: pairs with sum at most upper minus pairs with sum at most lower - 1.
  2. For a fixed limit, sort the array and use two pointers: if nums[l] + nums[r] <= limit, then all r - l pairs with this l and any j in (l, r] are valid.
  3. Advance l on success and decrement r otherwise.
  4. 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 to lower; the subtraction uses lower - 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems