Watch 10 video solutions for Count the Number of Fair Pairs, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCodeIO has 17,781 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.
A pair (i, j) is fair if:
0 <= i < j < n, andlower <= nums[i] + nums[j] <= upper
Example 1:
Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6 Output: 6 Explanation: 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 Explanation: There is a single fair pair: (2,3).
Constraints:
1 <= nums.length <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109Problem Overview: Given an integer array nums and two integers lower and upper, count the number of pairs (i, j) such that i < j and the sum nums[i] + nums[j] lies in the inclusive range [lower, upper]. The goal is to efficiently count valid pairs without checking every combination.
Approach 1: Brute Force (O(n²) time, O(1) space)
The simplest solution checks every pair of indices. Use two nested loops: the outer loop picks i, and the inner loop checks every j > i. For each pair, compute the sum and verify whether it falls between lower and upper. Increment the counter when the condition holds. This approach directly mirrors the problem definition and is easy to implement, but it becomes slow for large arrays because the number of comparisons grows quadratically.
Approach 2: Two-Pointer Technique after Sorting (O(n log n) time, O(1) extra space)
A more efficient strategy sorts the array first, which enables the use of the two pointers pattern. After sorting using a standard sorting algorithm, the problem reduces to counting how many pairs have sums within a range. Instead of checking every pair, compute the number of pairs with sum <= upper and subtract the number of pairs with sum < lower. Each of these counts can be found with a two-pointer sweep: place one pointer at the start and the other at the end of the array. If the sum is within the bound, every element between the pointers forms a valid pair with the left pointer, so add that count and move the left pointer forward. Otherwise move the right pointer backward. This linear scan after sorting avoids redundant checks and drastically reduces the runtime.
Some implementations replace the right pointer adjustment with a binary search to locate the valid range for each index, but the two-pointer sweep is typically faster in practice because it runs in a single pass.
Recommended for interviews: Start by describing the brute force solution to demonstrate understanding of the pair constraint. Then transition to the sorted two-pointer strategy. Interviewers usually expect the optimized approach because it reduces the complexity from O(n²) to O(n log n) due to sorting, with only a linear scan afterward.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small arrays or when demonstrating baseline logic in interviews |
| Sort + Two Pointers Range Counting | O(n log n) | O(1) extra | Preferred for large inputs; efficient pair counting after sorting |