Formatted question description: https://leetcode.ca/all/1885.html
1885. Count Pairs in Two Arrays
Level
Medium
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.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= 10^5
Solution
Create an array differences
with length n
such that differences[i] = nums1[i] - nums2[i]
for all 0 <= i < n
. Sort differences
. For each 0 <= i < n - 1
, find the minimum index
such that differences[index] + differences[i] > 0
, or index = n
if differences[n - 1] + differences[i] <= 0
, and the number of j
’s for the current i
is n - index
. In this way, the number of pairs of indices (i, j)
can be calculated.
class Solution {
public long countPairs(int[] nums1, int[] nums2) {
long count = 0;
int n = nums1.length;
int[] differences = new int[n];
for (int i = 0; i < n; i++)
differences[i] = nums1[i] - nums2[i];
Arrays.sort(differences);
for (int i = 0; i < n - 1; i++) {
int target = -differences[i] + 1;
int index = binarySearch(differences, n, target, i + 1);
count += n - index;
}
return count;
}
public int binarySearch(int[] differences, int n, int target, int startIndex) {
int low = startIndex, high = n - 1;
if (differences[high] < target)
return n;
while (low < high) {
int mid = (high - low) / 2 + low;
if (differences[mid] < target)
low = mid + 1;
else
high = mid;
}
return low;
}
}