2426. Number of Pairs Satisfying Inequality

Problem

You are given two 0-indexed integer arrays nums1 and nums2, each of size n, and an integer diff. Find the number of pairs (i, j) such that:

• 0 <= i < j <= n - 1 and

• nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

Return** the number of pairs that satisfy the conditions.**

  Example 1:

Input: nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
Output: 3
Explanation:
There are 3 pairs that satisfy the conditions:
1. i = 0, j = 1: 3 - 2 <= 2 - 2 + 1. Since i < j and 1 <= 1, this pair satisfies the conditions.
2. i = 0, j = 2: 3 - 5 <= 2 - 1 + 1. Since i < j and -2 <= 2, this pair satisfies the conditions.
3. i = 1, j = 2: 2 - 5 <= 2 - 1 + 1. Since i < j and -3 <= 2, this pair satisfies the conditions.
Therefore, we return 3.

Example 2:

Input: nums1 = [3,-1], nums2 = [-2,2], diff = -1
Output: 0
Explanation:
Since there does not exist any pair that satisfies the conditions, we return 0.

  Constraints:

• n == nums1.length == nums2.length

• 2 <= n <= 10^5

• -10^4 <= nums1[i], nums2[i] <= 10^4

• -10^4 <= diff <= 10^4

Solution (Java)

class Solution {
    private int[] helper;
    private int diff;
    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        int n = nums1.length;
        int[] n3 = new int[n];
        this.helper = new int[n];
        this.diff = diff;
        for (int i = 0; i < n; i++) {
            n3[i] = nums1[i] - nums2[i];
        }
        return mergeSort(n3, 0, n - 1);
    }
    public long mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int mid = start + (end - start) / 2;
        long count = mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end);
        for (int left = start, right = mid + 1; left <= mid; left++) {
            while (right <= end && nums[left] > nums[right] + diff) {
                right++;
            }
            count += end - right + 1; // find the first element larger or equal to the target we want 
        }
        // Arrays.sort(nums, start, end + 1);
        merge(nums, start, mid, end);
        return count;
    }
    public void merge(int[] nums, int start, int mid, int end) {
        int left = start;
        int right = mid + 1;
        int index = start;
        for (int i = start; i <= end; i++) {
            helper[i] = nums[i];
        } 
        while (left <= mid || right <= end) {
            if (left > mid) {
                nums[index++] = helper[right++];
            } else if (right <= end && helper[left] > helper[right]) {
                nums[index++] = helper[right++];
            } else {
                nums[index++] = helper[left++];
            }
        }
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).