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.
1function countFairPairs(nums, lower, upper) {
2 nums.sort((a, b) => a - b);
3 let count = 0;
4 for (let i = 0; i < nums.length; i++) {
5 let lowIndex = lowerBound(nums, i + 1, nums.length, lower - nums[i]);
6 let highIndex = upperBound(nums, i + 1, nums.length, upper - nums[i]);
7 count += highIndex - lowIndex;
8 }
9 return count;
10}
11
12function lowerBound(nums, start, end, target) {
13 let low = start, high = end;
14 while (low < high) {
15 let mid = low + Math.floor((high - low) / 2);
16 if (nums[mid] < target) low = mid + 1;
17 else high = mid;
18 }
19 return low;
20}
21
22function upperBound(nums, start, end, target) {
23 let low = start, high = end;
24 while (low < high) {
25 let mid = low + Math.floor((high - low) / 2);
26 if (nums[mid] <= target) low = mid + 1;
27 else high = mid;
28 }
29 return low;
30}
31
32const nums = [0, 1, 7, 4, 4, 5];
33const result = countFairPairs(nums, 3, 6);
34console.log(`Number of fair pairs: ${result}`);In JavaScript, the method employs sorting followed by binary searches implemented in helper functions that determine fair pairs within the bounds.
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
JavaScript's brute-force technique evaluates the sum of each pair of elements using nested loops to check if they satisfy the given range criteria.