Welcome to Subscribe On Youtube

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;
    }
}

############

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:
    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))



  • 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;
    }
};

  • 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