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.
This approach leverages sorting and a two-pointer technique to efficiently find the number of fair pairs. By sorting the array, we bring potential fair pairs closer, simplifying the conditions checking. Two pointers are then used to find suitable pairs within the bounds.
First, sort the array nums. As we iterate through each element as one half of the pair, use two pointers to find elements that complete the pair within the given range of sums.
This C implementation uses binary search after sorting the array. Two loops identify the lower and upper bounds of valid pair elements, and count their occurrences.
Time Complexity: O(n log n), where the sorting step dominates the complexity. Each binary search operation runs in O(log n).
Space Complexity: O(1), as we sort in-place.
A simpler, brute-force approach involves examining every possible pair (i, j) to determine if it fits the 'fair pair' criteria. While this method is easier to understand and implement, it becomes inefficient as the input size increases.
The brute-force C implementation iterates over each element and checks every subsequent element for compliant pair conditions. This straightforward iteration checks all n^2 pairs.
Time Complexity: O(n^2), as it examines every possible pair.
Space Complexity: O(1), since no additional space is utilized.
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.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique after Sorting | Time Complexity: O(n log n), where the sorting step dominates the complexity. Each binary search operation runs in O(log n). Space Complexity: O(1), as we sort in-place. |
| Approach 2: Brute Force | Time Complexity: O(n^2), as it examines every possible pair. Space Complexity: O(1), since no additional space is utilized. |
| Sorting + Binary Search | — |
| 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 |
Count the Number of Fair Pairs - Leetcode 2563 - Python • NeetCodeIO • 17,781 views views
Watch 9 more video solutions →Practice Count the Number of Fair Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor