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] <= 105We 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, cdots, 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 times log n), and the space complexity is O(n). Here, n is the length of the array.
Java
C++
Go
TypeScript
Rust
JavaScript
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,200 views views
Watch 9 more video solutions →Practice Count Pairs in Two Arrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor