LeetCode 2563 - Count the Number of Fair Pairs

LeetCode Problem 2563

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to count how many pairs of indices (i, j) satisfy two conditions:

1. i < j
2. The sum nums[i] + nums[j] lies within the inclusive range [lower, upper]

We are given an integer array nums and two bounds, lower and upper. The goal is to return the total number of valid index pairs.

The key detail is that we are counting pairs of indices, not distinct values. If the same value appears multiple times in the array, different index combinations count as different pairs.

For example, if nums = [1, 1, 1] and the target range includes 2, then all three index pairs are valid:

• (0,1)
• (0,2)
• (1,2)

The constraints are very important:

• nums.length can be as large as 10^5
• Values inside the array can be very large positive or negative integers
• lower and upper can also be very large

A naive nested loop would examine every possible pair, which requires O(n^2) time. With n = 100000, that would mean roughly 10^10 operations, which is far too slow.

The constraints strongly suggest that we need an algorithm around O(n log n).

Several edge cases are important:

• Arrays containing duplicate values
• Arrays containing negative numbers
• Cases where all pairs are valid
• Cases where no pairs are valid
• Very small arrays such as length 1
• Large integer sums that could overflow 32 bit integers in some languages

The problem guarantees that lower <= upper, so the valid range is always well defined.

Approaches

Brute Force

The most straightforward solution is to examine every possible pair (i, j) where i < j.

For each pair:

1. Compute nums[i] + nums[j]
2. Check whether the sum lies between lower and upper
3. Increment the answer if it does

This approach is correct because it explicitly checks every valid pair exactly once.

However, the array can contain up to 100000 elements. The number of possible pairs is:

$\frac{n(n-1)}{2}$

When n = 100000, this becomes approximately 5 * 10^9 pairs, which is far too large to process efficiently.

Optimal Approach

The key insight is that sorting transforms the problem into one where binary search or two pointers become useful.

Suppose the array is sorted.

For a fixed index i, we want to count how many indices j > i satisfy:

$lower \le nums[i] + nums[j] \le upper$

Rearranging gives:

$lower - nums[i] \le nums[j] \le upper - nums[i]$

Now the task becomes:

• Find the first position where nums[j] >= lower - nums[i]
• Find the first position where nums[j] > upper - nums[i]

Because the array is sorted, binary search can find these boundaries efficiently.

The number of valid partners for index i is simply:

right_boundary - left_boundary

Repeating this for every index gives an O(n log n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible pair directly
Optimal	O(n log n)	O(1) or O(log n)	Sorts array and uses binary search for valid ranges

Algorithm Walkthrough

1. Sort the array in nondecreasing order.

Sorting is important because binary search only works on ordered data. Once sorted, all values that satisfy a range condition become contiguous. 2. Initialize a variable count to store the total number of fair pairs. 3. Iterate through each index i from 0 to n - 1.

For each element nums[i], we want to determine how many later elements can form a valid pair with it. 4. Compute the minimum allowed partner value.

The pair must satisfy:

$nums[j] \ge lower - nums[i]$

So we binary search for the first index where this condition becomes true. 5. Compute the maximum allowed partner value.

The pair must also satisfy:

$nums[j] \le upper - nums[i]$

We binary search for the first index where values become greater than this limit. 6. Restrict searches to indices after i.

Since the problem requires i < j, we only search in the range [i + 1, n). 7. Add the number of valid indices to the answer.

If:

left = first valid index
right = first invalid index

then the count of valid partners is:

right - left

8. Continue until all indices are processed.
9. Return the total count.

Why it works

After sorting, all values satisfying a numeric range appear consecutively. For each fixed nums[i], the valid partner values form a continuous interval in the sorted array. Binary search correctly finds the boundaries of this interval, and subtracting the two boundaries gives the exact number of valid partners. Since every pair is counted once with i < j, the final result is correct.

Python Solution

from bisect import bisect_left, bisect_right
from typing import List

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        n = len(nums)

        fair_pairs = 0

        for i in range(n):
            min_value = lower - nums[i]
            max_value = upper - nums[i]

            left = bisect_left(nums, min_value, i + 1)
            right = bisect_right(nums, max_value, i + 1)

            fair_pairs += right - left

        return fair_pairs

The implementation begins by sorting the array. This enables efficient binary searching for valid partner ranges.

For each index i, the code computes the smallest and largest values that can pair with nums[i] while remaining within the target sum range.

bisect_left finds the first valid position where elements are at least min_value.

bisect_right finds the first position after all elements less than or equal to max_value.

The difference between these two indices gives the number of valid partners for the current element.

The search starts at i + 1 to ensure that only pairs with i < j are counted.

Finally, all counts are accumulated and returned.

Go Solution

package main

import (
	"sort"
)

func countFairPairs(nums []int, lower int, upper int) int64 {
	sort.Ints(nums)

	n := len(nums)
	var fairPairs int64 = 0

	for i := 0; i < n; i++ {
		minValue := lower - nums[i]
		maxValue := upper - nums[i]

		left := sort.Search(n, func(j int) bool {
			return j > i && nums[j] >= minValue
		})

		right := sort.Search(n, func(j int) bool {
			return j > i && nums[j] > maxValue
		})

		fairPairs += int64(right - left)
	}

	return fairPairs
}

The Go solution follows the same algorithmic idea as the Python version.

sort.Ints sorts the array in place.

Go does not provide built in bisect_left and bisect_right, so we use sort.Search to implement equivalent binary searches.

The answer is stored in int64 because the number of pairs can exceed the range of a 32 bit integer. In the worst case, the number of pairs is approximately 5 * 10^9.

Unlike Python integers, Go integers have fixed sizes, so explicit overflow handling is important.

Worked Examples

Example 1

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

After sorting:

nums = [0,1,4,4,5,7]

i	nums[i]	Required Range for nums[j]	Valid Indices	Count Added
0	0	[3, 6]	2, 3, 4	3
1	1	[2, 5]	2, 3, 4	3
2	4	[-1, 2]	none	0
3	4	[-1, 2]	none	0
4	5	[-2, 1]	none	0
5	7	[-4, -1]	none	0

Total:

3 + 3 = 6

Final answer:

6

Example 2

nums = [1,7,9,2,5]
lower = 11
upper = 11

After sorting:

nums = [1,2,5,7,9]

i	nums[i]	Required Range for nums[j]	Valid Indices	Count Added
0	1	[10, 10]	none	0
1	2	[9, 9]	4	1
2	5	[6, 6]	none	0
3	7	[4, 4]	none	0
4	9	[2, 2]	none	0

Total:

1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting costs O(n log n), each iteration performs binary searches
Space	O(1) or O(log n)	Depends on sorting implementation details

The dominant cost is sorting the array.

After sorting, each of the n iterations performs two binary searches, each costing O(log n) time.

Therefore, the total complexity is:

$O(n \log n)$

The algorithm uses only a few extra variables beyond the sorted array itself. Python's sorting implementation may use auxiliary stack space internally, which is why some analyses report O(log n) auxiliary space.

Test Cases

from typing import List

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        from bisect import bisect_left, bisect_right

        nums.sort()
        total = 0

        for i in range(len(nums)):
            left = bisect_left(nums, lower - nums[i], i + 1)
            right = bisect_right(nums, upper - nums[i], i + 1)
            total += right - left

        return total

sol = Solution()

assert sol.countFairPairs([0,1,7,4,4,5], 3, 6) == 6
# Provided example with multiple valid pairs

assert sol.countFairPairs([1,7,9,2,5], 11, 11) == 1
# Provided example with exactly one valid pair

assert sol.countFairPairs([1], 0, 10) == 0
# Single element, no possible pairs

assert sol.countFairPairs([1,1,1], 2, 2) == 3
# All duplicate values, every pair valid

assert sol.countFairPairs([-1,-2,-3], -5, -3) == 3
# Negative numbers only

assert sol.countFairPairs([10,20,30], 100, 200) == 0
# No valid pairs

assert sol.countFairPairs([0,0,0,0], 0, 0) == 6
# Every possible pair valid

assert sol.countFairPairs([-5,5], 0, 0) == 1
# Pair sum exactly equals boundary

assert sol.countFairPairs([1000000000,1000000000], 2000000000, 2000000000) == 1
# Large integer values

assert sol.countFairPairs([-10,0,10], -10, 10) == 3
# Mixed negative and positive values

Test	Why
[0,1,7,4,4,5]	Verifies standard mixed input
[1,7,9,2,5]	Verifies exact boundary matching
[1]	Verifies handling of arrays with no pairs
[1,1,1]	Verifies duplicate handling
[-1,-2,-3]	Verifies negative values
[10,20,30]	Verifies no valid pair scenario
[0,0,0,0]	Verifies all pairs valid
[-5,5]	Verifies exact lower and upper boundary equality
[1000000000,1000000000]	Verifies large integer arithmetic
[-10,0,10]	Verifies mixed sign values

Edge Cases

One important edge case is an array with fewer than two elements. Since a pair requires two distinct indices, no valid pair can exist. The implementation handles this naturally because the binary searches begin at i + 1, so no matches are ever found.

Another important case involves duplicate values. For example, [1,1,1] with target sum 2 contains three valid pairs. A buggy implementation might accidentally count unique values instead of unique index pairs. This solution counts index ranges after sorting, so every valid index combination is included correctly.

Negative numbers are also important because sorting and range calculations must work correctly across both positive and negative values. For example, with nums = [-3,-2,-1], valid sums may still fall inside the target range. The binary search logic works correctly because it depends only on sorted order, not on value signs.

A final important edge case involves very large integers. Since values can be as large as 10^9, pair sums may reach 2 * 10^9. In Go, the total number of valid pairs can exceed 32 bit integer limits, so the implementation stores the answer in int64 to avoid overflow.