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.
1using System;
2
3public class Solution {
4 public int CountFairPairs(int[] nums, int lower, int upper) {
5 Array.Sort(nums);
6 int count = 0;
7 for (int i = 0; i < nums.Length; i++) {
8 int lowBound = LowerBound(nums, i + 1, nums.Length, lower - nums[i]);
9 int upBound = UpperBound(nums, i + 1, nums.Length, upper - nums[i]);
10 count += upBound - lowBound;
11 }
12 return count;
13 }
14
15 private int LowerBound(int[] nums, int start, int end, int target) {
16 int low = start, high = end;
17 while (low < high) {
18 int mid = low + (high - low) / 2;
19 if (nums[mid] < target) low = mid + 1;
20 else high = mid;
21 }
22 return low;
23 }
24
25 private int UpperBound(int[] nums, int start, int end, int target) {
26 int low = start, high = end;
27 while (low < high) {
28 int mid = low + (high - low) / 2;
29 if (nums[mid] <= target) low = mid + 1;
30 else high = mid;
31 }
32 return low;
33 }
34
35 public static void Main() {
36 Solution sol = new Solution();
37 int[] nums = {0, 1, 7, 4, 4, 5};
38 int result = sol.CountFairPairs(nums, 3, 6);
39 Console.WriteLine("Number of fair pairs: " + result);
40 }
41}This C# solution sorts the array and performs binary search with LowerBound and UpperBound methods to find the number of valid pair elements efficiently.
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#include <vector>
class Solution {
public:
int countFairPairs(std::vector<int>& nums, int lower, int upper) {
int count = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
int sum = nums[i] + nums[j];
if (sum >= lower && sum <= upper) {
count++;
}
}
}
return count;
}
};
int main() {
Solution sol;
std::vector<int> nums = {0, 1, 7, 4, 4, 5};
int result = sol.countFairPairs(nums, 3, 6);
std::cout << "Number of fair pairs: " << result << std::endl;
return 0;
}This C++ implementation evaluates each potential pair from the start of the list using nested loops to find and count fair pairs.