#2563

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Count the Number of Fair Pairs

Efficiently count all fair pairs in an array using sorting and binary search, focusing on the sum range between lower and upper limits.

array two pointers binary search sorting

Problem Statement

Given a 0-indexed integer array nums of size n and two integers lower and upper, your task is to return the number of fair pairs in nums. A fair pair is defined as a pair of indices (i, j) such that 0 <= i < j < n and the sum nums[i] + nums[j] lies between lower and upper inclusive.

For example, given nums = [0,1,7,4,4,5], lower = 3, and upper = 6, there are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5). Constraints are 1 <= nums.length <= 10^5, -10^9 <= nums[i], lower, upper <= 10^9. Efficient algorithms must handle large arrays without timing out.

Examples

Example 1

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6

Output: 6

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

There is a single fair pair: (2,3).

Constraints

1 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109

Solution Approach

Sort and Prepare

Sort nums in ascending order. Sorting ensures that binary search can efficiently locate valid partner indices for each element, which is critical for this problem's sum range pattern.

Use Binary Search per Element

For each nums[i], perform two binary searches to find the first index j where nums[i]+nums[j] >= lower and the last index j where nums[i]+nums[j] <= upper. Count all j in this range to include all fair pairs.

Accumulate Fair Pair Counts

Iterate through all elements using the binary search results to sum the number of fair pairs. This approach leverages the valid answer space efficiently and avoids double counting by ensuring i < j.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Sorting takes O(n log n) time. Each element triggers two binary searches in O(log n), giving overall O(n log n) time. The space complexity is O(n) due to the sorted array copy or in-place sorting.

What Interviewers Usually Probe

Sorting the array is likely expected before counting pairs.
Look for using binary search to find the lower and upper sum bounds efficiently.
Handling edge cases where multiple elements produce the same sum is important.

Common Pitfalls or Variants

Common pitfalls

Failing to sort nums first, which breaks binary search assumptions.
Incorrectly counting pairs when i >= j or double counting identical sums.
Ignoring the constraints leading to solutions that exceed time limits for large n.

Follow-up variants

Count fair pairs where nums[i]*nums[j] falls within a range instead of sum.
Find fair pairs allowing i <= j instead of i < j, adjusting counting logic.
Return the actual list of fair pairs instead of just the count.

FAQ

What is a fair pair in this problem?

A fair pair (i, j) satisfies 0 <= i < j < n and lower <= nums[i] + nums[j] <= upper.

Why is sorting required for Count the Number of Fair Pairs?

Sorting allows binary search to find valid partner indices efficiently for each element, which reduces overall computation.

Can we use a two-pointer approach instead of binary search?

Yes, after sorting, a two-pointer method can scan the array to count fair pairs while maintaining i < j.

What is the time complexity of this solution?

Sorting takes O(n log n), and each element uses O(log n) binary searches, giving O(n log n) overall.

How does GhostInterview help avoid common pitfalls?

It provides guided binary search setup, shows correct counting rules for pairs, and prevents double counting for identical sums.

terminal

Solution

Solution 1: Sorting + Binary Search

First, we sort the array `nums` in ascending order. Then, for each `nums[i]`, we use binary search to find the lower bound `j` of `nums[j]`, i.e., the first index that satisfies `nums[j] >= lower - nums[i]`. Then, we use binary search again to find the lower bound `k` of `nums[k]`, i.e., the first index that satisfies `nums[k] >= upper - nums[i] + 1`. Therefore, `[j, k)` is the index range for `nums[j]` that satisfies `lower <= nums[i] + nums[j] <= upper`. The count of these indices corresponding to `nums[j]` is `k - j`, and we can add this to the answer. Note that $j > i$.

1

2

3

4

5

6

7

8

9

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        ans = 0
        for i, x in enumerate(nums):
            j = bisect_left(nums, lower - x, lo=i + 1)
            k = bisect_left(nums, upper - x + 1, lo=i + 1)
            ans += k - j
        return ans

Continue Practicing

#2576 find the maximum number of marked indices #2332 the latest time to catch a bus #2824 count pairs whose sum is less than target