Sponsored
Sponsored
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.
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.
1from typing import List
2
3class Solution:
4 def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
5 nums.sort()
6 count = 0
7 for i in range(len(nums)):
8 low_index = self.lowerBound(nums, i + 1, len(nums), lower - nums[i])
9 high_index = self.upperBound(nums, i + 1, len(nums), upper - nums[i])
10 count += high_index - low_index
11 return count
12
13 def lowerBound(self, nums: List[int], start: int, end: int, target: int) -> int:
14 low, high = start, end
15 while low < high:
16 mid = low + (high - low) // 2
17 if nums[mid] < target:
18 low = mid + 1
19 else:
20 high = mid
21 return low
22
23 def upperBound(self, nums: List[int], start: int, end: int, target: int) -> int:
24 low, high = start, end
25 while low < high:
26 mid = low + (high - low) // 2
27 if nums[mid] <= target:
28 low = mid + 1
29 else:
30 high = mid
31 return low
32
33# Test the implementation
34if __name__ == "__main__":
35 sol = Solution()
36 nums = [0, 1, 7, 4, 4, 5]
37 result = sol.countFairPairs(nums, 3, 6)
38 print(f"Number of fair pairs: {result}")Python's solution involves sorting and utilizing internal methods lowerBound and upperBound to localize and calculate fair pairs, iterating through the array.
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.
Time Complexity: O(n^2), as it examines every possible pair.
Space Complexity: O(1), since no additional space is utilized.
1
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.