Welcome to Subscribe On Youtube

1885. Count Pairs in Two Arrays

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 <= 105
• 1 <= nums1[i], nums2[i] <= 105

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public long countPairs(int[] nums1, int[] nums2) {
          int n = nums1.length;
          int[] d = new int[n];
          for (int i = 0; i < n; ++i) {
              d[i] = nums1[i] - nums2[i];
          }
          Arrays.sort(d);
          long ans = 0;
          for (int i = 0; i < n; ++i) {
              int left = i + 1, right = n;
              while (left < right) {
                  int mid = (left + right) >> 1;
                  if (d[mid] > -d[i]) {
                      right = mid;
                  } else {
                      left = mid + 1;
                  }
              }
              ans += n - left;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      long long countPairs(vector<int>& nums1, vector<int>& nums2) {
          int n = nums1.size();
          vector<int> d(n);
          for (int i = 0; i < n; ++i) d[i] = nums1[i] - nums2[i];
          sort(d.begin(), d.end());
          long long ans = 0;
          for (int i = 0; i < n; ++i) {
              int j = upper_bound(d.begin() + i + 1, d.end(), -d[i]) - d.begin();
              ans += n - j;
          }
          return ans;
      }
  };
  

• class Solution:
      def countPairs(self, nums1: List[int], nums2: List[int]) -> int:
          n = len(nums1)
          d = [nums1[i] - nums2[i] for i in range(n)]
          d.sort()
          return sum(n - bisect_right(d, -v, lo=i + 1) for i, v in enumerate(d))
  
  

• func countPairs(nums1 []int, nums2 []int) int64 {
  	n := len(nums1)
  	d := make([]int, n)
  	for i, v := range nums1 {
  		d[i] = v - nums2[i]
  	}
  	sort.Ints(d)
  	var ans int64
  	for i, v := range d {
  		left, right := i+1, n
  		for left < right {
  			mid := (left + right) >> 1
  			if d[mid] > -v {
  				right = mid
  			} else {
  				left = mid + 1
  			}
  		}
  		ans += int64(n - left)
  	}
  	return ans
  }
  

All Problems

All Solutions