Description
Given two integer arrays nums1 and nums2 of length n, count the pairs of indices (i, j) such that i < j and nums1[i] + nums1[j] > nums2[i] + nums2[j].
Return the number of pairs satisfying the condition.
Example 1:
Input: nums1 = [2,1,2,1], nums2 = [1,2,1,2]
Output: 1
Explanation: The pairs satisfying the condition are:
- (0, 2) where 2 + 2 > 1 + 1.
Example 2:
Input: nums1 = [1,10,6,2], nums2 = [1,4,1,5]
Output: 5
Explanation: The pairs satisfying the condition are:
- (0, 1) where 1 + 10 > 1 + 4.
- (0, 2) where 1 + 6 > 1 + 1.
- (1, 2) where 10 + 6 > 4 + 1.
- (1, 3) where 10 + 2 > 4 + 5.
- (2, 3) where 6 + 2 > 1 + 5.
Constraints:
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 105
Solutions
Solution 1: Sorting + Two Pointers
We can transform the inequality in the problem to nums1[i] - nums2[i] + nums1[j] - nums2[j] > 0, which simplifies to nums[i] + nums[j] > 0, where nums[i] = nums1[i] - nums2[i].
For the array nums, we need to find all pairs (i, j) that satisfy nums[i] + nums[j] > 0.
We can sort the array nums and then use the two-pointer method. Initialize the left pointer l = 0 and the right pointer r = n - 1. Each time, we check if nums[l] + nums[r] is less than or equal to 0. If it is, we move the left pointer to the right in a loop until nums[l] + nums[r] > 0. At this point, all pairs with the left pointer at l, l + 1, l + 2, …, r - 1 and the right pointer at r satisfy the condition, and there are r - l such pairs. We add these pairs to the answer. Then, move the right pointer to the left and continue the above process until l \ge r.
The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the length of the array.
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
nums = [a - b for a, b in zip(nums1, nums2)]
nums.sort()
l, r = 0, len(nums) - 1
ans = 0
while l < r:
while l < r and nums[l] + nums[r] <= 0:
l += 1
ans += r - l
r -= 1
return ans(code-box)
class Solution {
public long countPairs(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
nums[i] = nums1[i] - nums2[i];
}
Arrays.sort(nums);
int l = 0, r = n - 1;
long ans = 0;
while (l < r) {
while (l < r && nums[l] + nums[r] <= 0) {
++l;
}
ans += r - l;
--r;
}
return ans;
}
}(code-box)
class Solution {
public:
long long countPairs(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
nums[i] = nums1[i] - nums2[i];
}
ranges::sort(nums);
int l = 0, r = n - 1;
long long ans = 0;
while (l < r) {
while (l < r && nums[l] + nums[r] <= 0) {
++l;
}
ans += r - l;
--r;
}
return ans;
}
};(code-box)
func countPairs(nums1 []int, nums2 []int) (ans int64) {
n := len(nums1)
nums := make([]int, n)
for i, x := range nums1 {
nums[i] = x - nums2[i]
}
sort.Ints(nums)
l, r := 0, n-1
for l < r {
for l < r && nums[l]+nums[r] <= 0 {
l++
}
ans += int64(r - l)
r--
}
return
}(code-box)
function countPairs(nums1: number[], nums2: number[]): number {
const n = nums1.length;
const nums: number[] = [];
for (let i = 0; i < n; ++i) {
nums.push(nums1[i] - nums2[i]);
}
nums.sort((a, b) => a - b);
let ans = 0;
let [l, r] = [0, n - 1];
while (l < r) {
while (l < r && nums[l] + nums[r] <= 0) {
++l;
}
ans += r - l;
--r;
}
return ans;
}(code-box)
impl Solution {
pub fn count_pairs(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
let mut nums: Vec<i32> = nums1.iter().zip(nums2.iter()).map(|(a, b)| a - b).collect();
nums.sort();
let mut l = 0;
let mut r = nums.len() - 1;
let mut ans = 0;
while l < r {
while l < r && nums[l] + nums[r] <= 0 {
l += 1;
}
ans += (r - l) as i64;
r -= 1;
}
ans
}
}(code-box)
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var countPairs = function (nums1, nums2) {
const n = nums1.length;
const nums = [];
for (let i = 0; i < n; ++i) {
nums.push(nums1[i] - nums2[i]);
}
nums.sort((a, b) => a - b);
let ans = 0;
let [l, r] = [0, n - 1];
while (l < r) {
while (l < r && nums[l] + nums[r] <= 0) {
++l;
}
ans += r - l;
--r;
}
return ans;
};(code-box)
