2563. Count the Number of Fair Pairs - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given a zero-indexed array nums of size n and two integers lower and upper, we need to count the number of fair pairs in the array. A pair of indices (i, j) is considered fair if:

0 <= i < j < n (the pair indices are in range and i is smaller than j), and
the sum of the elements is within the given range, i.e. lower <= nums[i] + nums[j] <= upper.

In other words, we want to count all pairs of distinct indices whose values add up to a number between lower and upper (inclusive). If no such pairs exist, the result should be 0.

Examples:

Example 1:
- Input: nums = [0, 1, 7, 4, 4, 5], lower = 3, upper = 6
- Output: 6
- Explanation: There are 6 fair pairs. These valid pairs of indices (with their sum in brackets) are: (0,3) -> sum=0+4=4, (0,4) -> 0+4=4, (0,5) -> 0+5=5, (1,3) -> 1+4=5, (1,4) -> 1+4=5, and (1,5) -> 1+5=6. Each of these sums lies between 3 and 6 inclusive. (All other pairs either sum to less than 3 or more than 6.)
Example 2:
- Input: nums = [1, 7, 9, 2, 5], lower = 11, upper = 11
- Output: 1
- Explanation: There is only one fair pair: (2,3) because nums[2] + nums[3] = 9 + 2 = 11, which equals the target range [11, 11]. No other pair sums to 11 in this array.
Example 3:
- Input: nums = [-2, -1, 3, 4], lower = -1, upper = 2
- Output: 3
- Explanation: The fair pairs are: (0,2) -> sum = -2 + 3 = 1, (0,3) -> -2 + 4 = 2, and (1,2) -> -1 + 3 = 2. All these sums fall between -1 and 2. Other pairs either sum to less than -1 or greater than 2.

Constraints:

1 <= n <= 100,000 (where n is the length of nums)
-10^9 <= nums[i] <= 10^9 for each element in nums (values can be negative or positive)
-10^9 <= lower <= upper <= 10^9 (the range bounds can be negative or positive, and lower is not greater than upper)

Hints

Hint 1: A brute-force solution would involve checking every possible pair. However, consider the array size can be up to 100k elements – iterating over all pairs (which is ~10 billion pairs in the worst case) is far too slow. This hint suggests we need a more clever approach than checking each pair one by one.
Hint 2: Can sorting the array help in counting valid pairs more efficiently? Sorting might allow you to use two-pointer or binary search techniques to find pairs that fit the sum range without checking all pairs explicitly.
Hint 3: Think about how you would count the number of pairs with sum less than or equal to a certain value. If you can do that quickly, you could count pairs <= upper and subtract the count of pairs < lower (or <= lower-1) to get the number of pairs in the range [lower, upper]. This is a common trick to handle a range by using two simpler bounds.

Using these hints, you might realize that sorting combined with either the two-pointer technique or binary search can drastically reduce the complexity, making the problem tractable for large n. Try to outline how that would work before reading the full solution.

Multiple Approaches

Brute Force Approach

Idea: The brute-force method is straightforward: check every possible pair (i, j) and count those whose sum lies in the given range. This means double-looping through the array and testing the sum of each pair. While conceptually simple, this approach does a huge number of checks for large arrays, so it only works for small input sizes. Nonetheless, it’s useful to understand this baseline approach and verify correctness on small examples.

Explanation:

Initialize a counter count = 0.
Loop i from 0 to n-1. For each i, loop j from i+1 to n-1 (ensuring i < j to avoid duplicate pairs or using the same element twice).
For each pair (i, j), compute the sum s = nums[i] + nums[j]. If lower <= s <= upper, then this pair is fair – increment the counter.
After checking all pairs, count will hold the total number of fair pairs.
Return or output count.

Even though this approach is easy to implement, it will not scale to the maximum constraints (100k elements) because it requires on the order of $n^2$ pair checks. For n = 100,000, $n^2$ is $10^{10}$ , which is far beyond what can run in reasonable time. We include it here mainly for completeness and to illustrate the logic on small inputs.

Python Implementation (Brute Force):

Python3

. . . .

Java Implementation (Brute Force):

Java

. . . .

Complexity Analysis (Brute Force):

Time Complexity: $O(n^2)$ . We are double looping through the array, which leads to quadratic time. For large n (like 100k), this is infeasible. However, for very small arrays or constrained versions of the problem, this approach works correctly.
Space Complexity: $O(1)$ . We only use a constant amount of extra space (for counters and indices). The array is used in-place.

This brute-force approach clearly cannot handle the upper limits of the input size due to time complexity. We need to optimize it by reducing the number of pairs we check explicitly. This is where sorting and more clever counting methods come in.

Optimized Approach (Sorting + Two Pointers / Binary Search)

Idea: The main optimization is to sort the array first, which allows us to find pairs that meet the sum criteria much faster than brute force. Once the array is sorted, we can use either a two-pointer technique or binary search to count the valid pairs without examining each pair individually. The key observation is that if the array is sorted, for any fixed first element nums[i], the possible second elements that form a valid sum will occupy a contiguous segment in the sorted order. This lets us find the boundaries of that segment efficiently.

Approach Explanation:

Sort the array nums. Sorting takes $O(n \log n)$ time. After sorting, if we take any element nums[i] as the first element of the pair, then to satisfy lower <= nums[i] + nums[j] <= upper, the second element nums[j] must lie between lower - nums[i] and upper - nums[i] (inclusive). Because the array is sorted, all valid nums[j] for a given i will be grouped together in one continuous range of indices.
Find the range of valid second indices for each i. For each index i from 0 to n-1, we want to find:
- The smallest index j such that j > i and nums[i] + nums[j] >= lower. (This ensures the sum is not too low.)
- The largest index k (or more conveniently, one past the largest index) such that nums[i] + nums[k] <= upper. (This ensures the sum is not too high.)
  All indices between j and k (inclusive of j and inclusive of k if we consider k as the last valid index) will form a fair pair with i. The number of such indices is k - j (if k is one past the last valid index, or k - j + 1 if k is inclusive last index; we’ll handle it carefully in implementation).
Counting using two pointers or binary search:
- Two-pointer method: We can maintain two pointers, one (let’s call it left) moving from the start of the array and another (right) starting from the end. We can adjust these pointers based on the sum compared to the bounds. However, an easier way with two pointers is often to count pairs <= X and do it twice (for upper and for lower-1) as hinted earlier. Specifically, one can create a helper function to count how many pairs have sum <= a given value T in $O(n)$ time by a two-pointer sweep, and then do count(<=upper) - count(< lower) (which is the same as count(<= upper) - count(<= lower-1)). This avoids needing an inner loop entirely.
- Binary search method: For each i, use binary search to directly find the indices j and k described above. Many languages have library functions for binary search. For example, in Python we can use bisect_left to find the insertion point for a value. In Java, we can use Arrays.binarySearch or write a small binary search to find the lower bound. This approach will take $O(n \log n)$ time (binary search for each of the n elements).
Both methods ultimately achieve much better than O(n^2). The two-pointer approach can actually achieve O(n) after sorting (for each counting pass), making the total O(n \log n + n), while the binary search approach is O(n \log n). In terms of big-O, both are acceptable given n \log n dominates and n \log n with n=100k is quite feasible.

We will illustrate the binary search approach for clarity: For each index i, we find j = first index > i where nums[j] >= lower - nums[i] and k = first index > i where nums[k] > upper - nums[i]. Then all indices from j (inclusive) up to k-1 (inclusive) are valid partners for i. We then add (k - j) to our count (if k is one past last valid index). If at any point j goes beyond the array length or j <= i, it means there are no valid j for that i. We must also ensure we only count when j > i (so we don't pair an element with itself or revisit a pair in reverse order). Sorting inherently helps avoid double counting because we always enforce i < j.

Python Implementation (Optimized – Sorting + Binary Search):

Python3

. . . .

Explanation: We use Python’s bisect_left function from the built-in bisect module. The call bisect_left(nums, X, lo=i+1, hi=n) finds the insertion point for X in the sorted list nums[i+1:n] (i.e., it finds the first index in that subarray where the value is not less than X). For j, we use X = lower - value to find the first index where nums[j] is at least lower - nums[i]. For k, we use X = upper - value + 1 to find the first index where nums[k] is greater than upper - nums[i] (so k will be one index past the last valid value that could pair with nums[i]). The difference k - j gives the count of indices in [j, k) range, which are those satisfying lower - value <= nums[idx] < upper - value + 1, which is exactly lower <= value + nums[idx] <= upper. We accumulate this count for each i. The use of lo=i+1 ensures we never pair an element with itself or with any index <= i (avoiding repeats).

Java Implementation (Optimized – Sorting + Two Pointers/Binary Search):

Java

. . . .

Explanation: We wrote a custom lowerBound function (similar to C++'s std::lower_bound) to find the leftmost index where a target can be inserted. This is used to find j and k indices analogous to the Python solution. We sort nums using Arrays.sort. Then for each index i, we compute the range of valid j indices as described. We use long for totalPairs and also for sum calculations if needed, because the count of pairs can exceed the range of a 32-bit integer (e.g., in the worst case ~5e10 pairs for n=100k). The condition if (j < n) checks that there is at least one index where the second element could start. If j is beyond the array length, it means no valid partner for that i. We then add k - j to the count (cast to long to avoid overflow).

Complexity Analysis (Optimized Solution):

Time Complexity: $O(n \log n)$ in the worst case. Sorting the array takes $O(n \log n)$ , and then for each of the n elements we are doing either a two-pointer movement or two binary search operations. Two binary searches per element is $O(\log n)$ each, so that's $O(n \log n)$ for the scanning phase. In practice, this is efficient for $n=100k$ . The two-pointer alternative approach would take $O(n)$ for counting <= upper and another $O(n) for <= lower-1$ , plus sorting, still overall $O(n \log n)$ .
Space Complexity: $O(1)$ additional (or $O(n)$ if we consider the memory used by sorting algorithms in worst case). We sort the array in-place (both Python’s .sort() and Java’s Arrays.sort will sort in place), so we don't use extra arrays proportional to n. The only extra space used is a few variables (j, k, counters) and possibly stack space for sorting. If memory is a concern, we are already keeping usage minimal; there’s not much more to optimize here in terms of space.

Note: The result (count of pairs) can be a very large number (on the order of $n^2$ in the worst scenario). In Python, integers can grow arbitrarily, but in Java (and other languages) make sure to use a 64-bit type (like long) to store the count and to handle sums if needed. The sum of two minimum -1 $e$ 9 values is -2 $e$ 9 and two maximum 1 $e$ 9 values is 2 $e$ 9, which fits in a 32-bit int, but the count of pairs can exceed 32-bit range.

Step-by-Step Walkthrough

Let’s walk through an example step by step using the optimized approach (sorting + binary search) to see how it counts fair pairs. We’ll use Example 1 for illustration: nums = [0, 1, 7, 4, 4, 5], lower = 3, upper = 6.

Step 1: Sort the array.
The sorted array is nums = [0, 1, 4, 4, 5, 7]. (We keep track of original indices only conceptually; for counting pairs it’s easier to work with sorted positions.)

Step 2: Initialize count = 0. We will iterate through each index i and find how many j’s can pair with it.

Step 3: Iterate i from 0 to n-1:

i = 0, nums[i] = 0:
- Compute the needed range for the second element: it must be between lower - nums[i] = 3 - 0 = 3 and upper - nums[i] = 6 - 0 = 6 (inclusive) for the sum to be in [3,6].
- In the sorted array, we look at indices > 0. What is the first index where the value is ≥ 3? Scanning the sorted list: at index 0 the value is 0 (too low), index 1 is 1 (too low), index 2 is 4 (this is ≥3). So j = 2.
- Next, find the first index where the value is > 6 (one more than 6). We scan from index 2 onwards: value 4 <=6, next 4 <=6, 5 <=6, 7 > 6. The first index with value >6 is index 5 (value 7). So we set k = 5. (If we were using code, k is actually the index to insert 7, which would also be 5 in this case.)
- All indices from 2 up to 4 are valid j for i=0. These are indices 2, 3, and 4 corresponding to values [4, 4, 5]. We count them: that’s k - j = 5 - 2 = 3 pairs: specifically pairs (i,j) = (0,2), (0,3), (0,4). We add 3 to our count. (These pairs sum to 4, 4, and 5 respectively, all within [3,6].)
- Count so far = 3.
i = 1, nums[i] = 1:
- The second element must be between lower - 1 = 2 and upper - 1 = 5 inclusive.
- In the sorted array from index 2 onward, the first value ≥ 2 is at index 2 (value 4 is ≥ 2, actually we skipped value 1 at index1 itself since i=1). So j = 2.
- The first value > 5 (one more than 5) from index 2 on: value 4 <=5, next 4 <=5, 5 <=5, 7 >5, so that happens at index 5 again. So k = 5.
- Valid j indices are 2, 3, 4 (values [4,4,5]) again. That’s 5 - 2 = 3 new pairs: (1,2), (1,3), (1,4). We add 3.
- Count so far = 3 (previous) + 3 = 6.
i = 2, nums[i] = 4:
- The second element must be between lower - 4 = -1 and upper - 4 = 2.
- Starting from index 3, the first value ≥ -1 is actually at index 3 itself (value 4, since everything is ≥ -1 obviously). So j = 3.
- The first value > 2 from index 3 onward: at index 3 the value is 4, which is already > 2. That means even the smallest candidate is too large. So k = 3 (index 3 is where value exceeds 2, essentially the insertion position for any value >2 is 3).
- Now j = 3 and k = 3. The range [j, k) is empty (because j == k, there are no indices between 3 and 2). This indicates zero valid pairs with i=2. Another way: since nums[i] is already 4, adding any other number (which are ≥4 sorted) will make sum >= 8, so definitely out of [3,6]. So we add 0.
- Count remains = 6.
i = 3, nums[i] = 4 (the second 4 in the array):
- Second element must be between lower - 4 = -1 and upper - 4 = 2, the same range as for i=2. We start checking from index 4. The first value ≥ -1 at or after 4 is index 4 itself (5, which is >2 actually). So effectively, any available j is too large. We find j = 4, and then immediately see that value at 4 is 5 which is >2, so k = 4. No valid range (j == k).
- Count remains = 6 (no new pairs).
i = 4, nums[i] = 5:
- The second element must be between lower - 5 = -2 and upper - 5 = 1. We check from index 5 onwards. The first index ≥ -2 is 5 (value 7, which is >1). So j = 5, but the value at 5 is already out of range (>1), meaning k = 5 as well (no value ≤1 at or beyond index 5). No valid second element for i=4.
- Count remains = 6.
i = 5, nums[i] = 7:
- This is the last element. Any pair would require another element with index >5, but none exists. We can stop here. (Our loop would naturally end here anyway.)

Step 4: Final count. We have accumulated a total count of 6 fair pairs, which matches the expected answer. We effectively found all the pairs listed in the example explanation by this method. Notice how once i became large enough (value too high), the range [lower - nums[i], upper - nums[i]] shifted such that no j could satisfy it, and the algorithm naturally yielded zero for those cases and continued. This demonstrates the efficiency — we did not check every pair explicitly; we mostly did comparisons and a couple of pointer jumps or binary searches per element.

This walkthrough shows how the algorithm efficiently finds the range of valid partners for each element after sorting. The use of binary search (or two pointers) skips over large swaths of pairs that would have been invalid, instead of checking them one by one.

Common Mistakes & Edge Cases

When solving this problem, there are several common pitfalls to be aware of:

Forgetting to sort the array: The optimized approach crucially relies on the array being sorted. If you forget to sort, two-pointer or binary search methods will not work correctly, since they assume the array order to skip invalid pairs.
Using the two-pointer technique incorrectly: If using two pointers to count pairs <= X, one must be careful to reset or move pointers correctly. A common mistake is trying to do a double-pointer in one pass for both the lower and upper bound simultaneously – it’s easier and less error-prone to do two separate counts (for upper and lower-1). Also, ensure one pointer starts at the beginning and the other at the end, and that you move the correct pointer based on the sum comparison.
Double counting pairs or counting i with itself: Ensure that each pair is counted only once. By always enforcing i < j (for example, starting inner loops or searches from i+1), we avoid counting the same pair twice in opposite orders or pairing an element with itself.
Off-by-one errors in binary search bounds: When using binary search to find the boundary indices (j and k), it’s easy to make an off-by-one error. For example, one might mistakenly search for upper - nums[i] instead of upper - nums[i] + 1 for the upper bound. Remember that if you want the last index where nums[i] + nums[j] is <= upper, searching for upper - nums[i] + 1 gives you the first index where it’s greater, which is the correct k. Pay careful attention to inclusive vs exclusive range when using binary search.
Not using the right data type for counting: As noted, the number of pairs can be very large (on the order of $n^2/2). In Java or C++, using an int for the count may overflow. Always use a larger type (long` in Java/C++ or Python’s built-in int which can expand) for the pair count.
Ignoring negative values: If implementing the two-pointer approach for counting pairs <= X, one might assume that if the smallest plus largest is below X, then moving the left pointer up is needed, etc. This logic should still hold even if numbers are negative (the sorted order takes care of it), but be cautious. For example, if all numbers are very negative and lower and upper are also negative, the logic still works, but ensure you handle the calculations properly (e.g., lower - nums[i] could overflow in some languages if not using a big enough type).
Edge case – no pairs at all: If the array has length 1, or if no two numbers can sum into the range, the answer should correctly come out as 0. Our algorithms naturally handle this (the brute force will never find a pair, the optimized will either not find any valid j for each i). Just be sure to return 0 in those cases rather than, say, an uninitialized value.

By being mindful of these issues, you can avoid common bugs. It often helps to test your solution on edge cases: sorted input, reverse sorted input, all elements the same, all elements such that every pair is valid (to test large counts), or no pair is valid, as well as including negative numbers.

This problem is about pair counting with sum conditions. There are several related problems and possible variations:

Two Sum (LeetCode #1, Easy): Instead of counting pairs in a range, the classic two-sum problem asks if there exists a pair that sums to exactly a given target (and often to return the indices). The approach for that problem can use a hash set/map to find complements in one pass, or sorting + two-pointer to find one pair. It’s simpler than fair pairs because it only cares about one exact sum and just finding one pair (not counting all).
Two Sum II – Input Array Is Sorted (LeetCode #167, Easy): This is a variant of Two Sum where the array is already sorted, and you need to find one pair that adds up to a target. The typical solution uses the two-pointer technique from both ends to find the target sum in linear time. It’s related because it uses the sorted two-pointer idea, though for finding a pair rather than counting many pairs.
Two Sum Less Than K (LeetCode #1099, Easy/Medium): Given an array and an integer K, find the maximum sum of any pair that is < K (or return -1 if none). This problem also uses sorting and two pointers: you move pointers to try to get as close to K as possible without exceeding it. It’s a different goal (optimizing the sum rather than counting), but it’s in a similar spirit of pair-sum problems with a constraint.
Count Pairs with Sum Less Than Target (LeetCode #2824, Easy): This is a simpler version of the fair pairs count problem. It asks to count how many pairs have a sum strictly less than a given target. You can solve it with a similar approach (sort and two-pointer from ends counting pairs). In fact, counting pairs <= X is a sub-step we used in the fair pairs solution.
3Sum (LeetCode #15, Medium): This extends the two-sum problem to three elements: find all unique triplets that sum to zero. The typical solution sorts the array and then uses a two-pointer technique inside a loop to fix the first element, effectively reducing it to a two-sum problem for each fixed first element. It’s related by technique (sorting and two pointers), though here we need to output the actual triplets, not just count them, and it’s for a fixed target (0 in the classic version).
3Sum Smaller (LeetCode #259, Medium): This problem asks to count the number of triplets (i, j, k) with i<j<k such that the sum of the three numbers is less than a given target. The approach is an extension of what we discussed: sort the array, then for each index, use two pointers to count two-sum combinations that fit the criteria with the current index. It’s more complex in terms of triple loop, but sorting + two-pointer makes it efficient ( $O(n^2)$ ). It’s a good next step if you want to practice counting combinations with sum constraints.
Variations of Fair Pairs: The fair pairs question could be tweaked. For example, if the problem asked for listing the fair pairs rather than counting, we would potentially generate a large output (which might be infeasible for large n). The approach would be similar (we’d find the ranges of j for each i), but storing or outputting them could be expensive. Another variation could be requiring the sum to be exactly within a range but maybe with other conditions (like distinct values or something), but those would be different constraints on how you count.

2563. Count the Number of Fair Pairs - Detailed Explanation

Problem Statement

Hints

Multiple Approaches

Brute Force Approach

Optimized Approach (Sorting + Two Pointers / Binary Search)

Step-by-Step Walkthrough

Common Mistakes & Edge Cases

Alternative Variations & Related Problems