Problem Description

You are given a 0-indexed integer array nums of size n and two integers lower and upper. Your task is to count the number of "fair pairs" in the array.

A pair (i, j) is considered fair if it satisfies both of the following conditions:

1. The indices must satisfy 0 <= i < j < n (meaning i comes before j in the array)
2. The sum of the elements at these indices must be within the given range: lower <= nums[i] + nums[j] <= upper

For example, if nums = [0, 1, 7, 4], lower = 3, and upper = 6:

• Pair (0, 1): nums[0] + nums[1] = 0 + 1 = 1, which is not in range [3, 6] - not fair
• Pair (0, 2): nums[0] + nums[2] = 0 + 7 = 7, which is not in range [3, 6] - not fair
• Pair (0, 3): nums[0] + nums[3] = 0 + 4 = 4, which is in range [3, 6] - fair
• Pair (1, 2): nums[1] + nums[2] = 1 + 7 = 8, which is not in range [3, 6] - not fair
• Pair (1, 3): nums[1] + nums[3] = 1 + 4 = 5, which is in range [3, 6] - fair
• Pair (2, 3): nums[2] + nums[3] = 7 + 4 = 11, which is not in range [3, 6] - not fair

So the answer would be 2 fair pairs.

The solution uses sorting and binary search to efficiently count fair pairs. After sorting the array, for each element nums[i], it finds the range of valid nums[j] values (where j > i) that would create a sum within [lower, upper]. This is done by finding indices using binary search: the smallest index j where nums[j] >= lower - nums[i] and the smallest index k where nums[k] >= upper - nums[i] + 1. The count of valid pairs with nums[i] as the first element is then k - j.

Intuition

The naive approach would be to check every possible pair (i, j) where i < j, calculate their sum, and count how many fall within [lower, upper]. This would take O(n²) time, which might be too slow for large arrays.

The key insight is that once we fix the first element nums[i], we're looking for all nums[j] (where j > i) such that:

• lower <= nums[i] + nums[j] <= upper

We can rearrange this inequality to isolate nums[j]:

• lower - nums[i] <= nums[j] <= upper - nums[i]

This means for a fixed nums[i], we need to count how many elements in the remaining array fall within the range [lower - nums[i], upper - nums[i]].

If the array is sorted, all valid nums[j] values will form a contiguous segment. Why? Because in a sorted array, if some nums[j] satisfies nums[j] >= lower - nums[i], then all elements after it that are still <= upper - nums[i] will also be valid.

This leads us to use binary search on a sorted array:

1. Sort the array first
2. For each nums[i], find the leftmost position where nums[j] >= lower - nums[i] (this is the start of valid range)
3. Find the leftmost position where nums[j] >= upper - nums[i] + 1 (this is one position past the end of valid range)
4. The count of valid pairs with nums[i] as the first element is the difference between these two positions

The reason we search for upper - nums[i] + 1 instead of upper - nums[i] is because we want to find the first element that's too large to be valid, which gives us the exclusive upper bound of our range.

By sorting once (O(n log n)) and using binary search for each element (O(n log n) total), we achieve an overall time complexity of O(n log n), which is much better than the naive O(n²) approach.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation follows the sorting and binary search strategy outlined in the reference approach:

Step 1: Sort the array

nums.sort()

We sort the array in ascending order to enable binary search. This allows us to efficiently find ranges of valid pairs.

Step 2: Initialize counter

ans = 0

This variable will accumulate the total count of fair pairs.

Step 3: Iterate through each element as the first element of the pair

for i, x in enumerate(nums):

We iterate through each element x (which is nums[i]) that will serve as the first element in our pair (i, j).

Step 4: Find the lower bound of valid second elements

j = bisect_left(nums, lower - x, lo=i + 1)

Using bisect_left, we find the smallest index j where nums[j] >= lower - x. The parameter lo=i + 1 ensures we only search among indices greater than i (to maintain i < j). This gives us the starting position of valid nums[j] values.

Step 5: Find the upper bound of valid second elements

k = bisect_left(nums, upper - x + 1, lo=i + 1)

We find the smallest index k where nums[k] >= upper - x + 1. This gives us the first position that's beyond our valid range. Again, lo=i + 1 ensures we only look at indices after i.

Step 6: Count valid pairs for current nums[i]

ans += k - j

The number of valid nums[j] values is k - j. These are all the elements in the range [j, k) that, when paired with nums[i], produce a sum within [lower, upper].

Why this works:

• For a fixed nums[i], we need nums[j] such that lower - nums[i] <= nums[j] <= upper - nums[i]
• In the sorted array, all such nums[j] form a contiguous segment from index j to index k-1
• bisect_left(nums, lower - x, lo=i + 1) finds where this segment starts
• bisect_left(nums, upper - x + 1, lo=i + 1) finds where this segment ends (exclusive)
• The difference k - j gives us the count of valid pairs with nums[i] as the first element

Time Complexity: O(n log n) - sorting takes O(n log n), and we perform two binary searches for each of the n elements, resulting in O(n log n) for the search operations.

Space Complexity: O(1) or O(n) depending on the sorting algorithm used (Python's sort uses Timsort which can use up to O(n) auxiliary space).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

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

Step 1: Sort the array After sorting: nums = [0, 1, 4, 4, 5, 7]

Step 2: Process each element as the first element of a pair

Let's trace through each iteration:

i = 0, x = 0:

• Need to find nums[j] where 3 - 0 <= nums[j] <= 6 - 0
• So we need 3 <= nums[j] <= 6
• j = bisect_left([1, 4, 4, 5, 7], 3, lo=1) = 2 (first element >= 3 is at index 2, which is 4)
• k = bisect_left([1, 4, 4, 5, 7], 7, lo=1) = 5 (first element >= 7 is at index 5, which is 7)
• Valid pairs with nums[0]=0: indices 2, 3, 4 (values 4, 4, 5)
• Count: 5 - 2 = 3 pairs

i = 1, x = 1:

• Need nums[j] where 3 - 1 <= nums[j] <= 6 - 1
• So we need 2 <= nums[j] <= 5
• j = bisect_left([4, 4, 5, 7], 2, lo=2) = 2 (first element >= 2 is at index 2, which is 4)
• k = bisect_left([4, 4, 5, 7], 6, lo=2) = 5 (first element >= 6 is at index 5, which is 7)
• Valid pairs with nums[1]=1: indices 2, 3, 4 (values 4, 4, 5)
• Count: 5 - 2 = 3 pairs

i = 2, x = 4:

• Need nums[j] where 3 - 4 <= nums[j] <= 6 - 4
• So we need -1 <= nums[j] <= 2
• j = bisect_left([4, 5, 7], -1, lo=3) = 3 (all elements are >= -1)
• k = bisect_left([4, 5, 7], 3, lo=3) = 3 (no elements in range [3,∞) starting from index 3 are < 3)
• Valid pairs with nums[2]=4: none (no values in our range)
• Count: 3 - 3 = 0 pairs

i = 3, x = 4:

• Need nums[j] where -1 <= nums[j] <= 2
• j = bisect_left([5, 7], -1, lo=4) = 4
• k = bisect_left([5, 7], 3, lo=4) = 4
• Valid pairs with nums[3]=4: none
• Count: 4 - 4 = 0 pairs

i = 4, x = 5:

• Need nums[j] where 3 - 5 <= nums[j] <= 6 - 5
• So we need -2 <= nums[j] <= 1
• j = bisect_left([7], -2, lo=5) = 5
• k = bisect_left([7], 2, lo=5) = 5
• Valid pairs with nums[4]=5: none
• Count: 5 - 5 = 0 pairs

i = 5, x = 7:

• This is the last element, so no pairs can be formed (no j > i exists)

Total fair pairs: 3 + 3 + 0 + 0 + 0 = 6

The fair pairs are:

• (0,4): 0 + 4 = 4 ✓
• (0,4): 0 + 4 = 4 ✓ (second 4)
• (0,5): 0 + 5 = 5 ✓
• (1,4): 1 + 4 = 5 ✓
• (1,4): 1 + 4 = 5 ✓ (second 4)
• (1,5): 1 + 5 = 6 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity consists of two main parts:

• Sorting the array takes O(n × log n) time
• The for loop runs n times, and within each iteration:
  • bisect_left is called twice, each taking O(log n) time for binary search
  • Other operations are O(1)
  • Total per iteration: O(log n)
• Overall loop complexity: O(n × log n)

Since both sorting and the loop have O(n × log n) complexity, the total time complexity is O(n × log n).

Space Complexity: O(log n)

The space complexity comes from:

• The sorting algorithm (typically Timsort in Python) uses O(log n) space for its recursion stack
• The variables ans, i, x, j, and k use O(1) space
• No additional data structures are created

Therefore, the total space complexity is O(log n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Handle the Index Constraint After Sorting

The Problem: After sorting the array, the original indices are lost. A common mistake is to think that we still need to maintain the original i < j constraint from the problem statement. This leads to incorrect implementations where developers try to track original indices or apply unnecessary filtering.

Why It Happens: The problem states that pairs (i, j) must satisfy 0 <= i < j < n, which refers to indices in the original array. After sorting, some might think they need to preserve this original ordering relationship.

The Correct Understanding: Once we sort the array, we're working with a new arrangement. The constraint i < j in the sorted array is sufficient because:

• We're counting pairs, not returning the actual index pairs
• Any pair of distinct elements will be counted exactly once (when the smaller index is i and the larger is j)
• The sum nums[i] + nums[j] is the same regardless of which element comes first in the original array

Pitfall 2: Incorrect Boundary Calculation for Binary Search

The Problem: Using bisect_right instead of bisect_left for finding the upper boundary, or incorrectly calculating the search target as upper - num instead of upper - num + 1.

Incorrect Implementation:

# WRONG: This will include elements where nums[j] == upper - num
right_bound = bisect_right(nums, upper - num, lo=i + 1)

Why It's Wrong: We want to find the first index where nums[j] > upper - num, which is equivalent to finding where nums[j] >= upper - num + 1. Using bisect_right with upper - num would give us the position after all elements equal to upper - num, but this doesn't correctly handle the case when no such elements exist.

Correct Implementation:

# CORRECT: Find first position where nums[j] >= upper - num + 1
right_bound = bisect_left(nums, upper - num + 1, lo=i + 1)

Pitfall 3: Off-by-One Error in Binary Search Range

The Problem: Using lo=i instead of lo=i+1 in the binary search calls, which would allow pairing an element with itself.

Incorrect Implementation:

# WRONG: This allows i == j, counting an element paired with itself
left_bound = bisect_left(nums, lower - num, lo=i)

Why It's Wrong: The problem requires i < j, meaning we cannot pair an element with itself. Starting the search from i would include nums[i] in the potential partners for itself when 2 * nums[i] falls within [lower, upper].

Correct Implementation:

# CORRECT: Start searching from i+1 to ensure i < j
left_bound = bisect_left(nums, lower - num, lo=i + 1)

Pitfall 4: Integer Overflow in Languages with Fixed Integer Size

The Problem: In languages like Java or C++, calculating nums[i] + nums[j] directly might cause integer overflow if the values are large.

Solution for Other Languages:

# In Python, this is not an issue due to arbitrary precision integers
# But in Java/C++, you might need to rearrange the comparison:
# Instead of: nums[i] + nums[j] <= upper
# Use: nums[j] <= upper - nums[i]
# This avoids the addition that could overflow

Example Demonstrating Pitfall 2:

Consider nums = [1, 2, 3], lower = 3, upper = 4:

• For nums[0] = 1, we want pairs where 3 <= 1 + nums[j] <= 4
• This means 2 <= nums[j] <= 3
• Valid values are nums[1] = 2 and nums[2] = 3

With incorrect boundary:

• bisect_right(nums, 3, lo=1) returns 3 (position after the last 3)
• bisect_left(nums, 2, lo=1) returns 1
• Count: 3 - 1 = 2 ✓ (happens to work in this case)

But consider nums = [1, 2, 3, 4], lower = 3, upper = 4:

• For nums[0] = 1, we want 2 <= nums[j] <= 3
• bisect_right(nums, 3, lo=1) returns 3
• But bisect_left(nums, 4, lo=1) would give us 3 as well
• This wouldn't correctly exclude nums[3] = 4

With correct boundary:

• bisect_left(nums, upper - num + 1, lo=1) = bisect_left(nums, 4, lo=1) = 3
• This correctly identifies that index 3 is the first position outside our valid range