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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), as it examines every possible pair.
Space Complexity: O(1), since no additional space is utilized.
| 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. |
Count the Number of Fair Pairs - Leetcode 2563 - Python • NeetCodeIO • 15,313 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