2426. Number of Pairs Satisfying Inequality LeetCode Solution

In this guide, you will get 2426. Number of Pairs Satisfying Inequality LeetCode Solution with the best time and space complexity. The solution to Number of Pairs Satisfying Inequality problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Pairs Satisfying Inequality solution in C++
Number of Pairs Satisfying Inequality solution in Java
Number of Pairs Satisfying Inequality solution in Python
Additional Resources

2426. Number of Pairs Satisfying Inequality LeetCode Solution image

Problem Statement of Number of Pairs Satisfying Inequality

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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

2426. Number of Pairs Satisfying Inequality LeetCode Solution in C++

class Solution {
 public:
  long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
    // nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff
    // nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff
    // Define arr[i] := nums1[i] - nums2[i] -> arr[i] <= arr[j] + diff
    vector<int> arr;

    for (int i = 0; i < nums1.size(); ++i)
      arr.push_back(nums1[i] - nums2[i]);

    long ans = 0;
    mergeSort(arr, 0, arr.size() - 1, diff, ans);
    return ans;
  }

 private:
  void mergeSort(vector<int>& arr, int l, int r, int diff, long& ans) {
    if (l >= r)
      return;

    const int m = (l + r) / 2;
    mergeSort(arr, l, m, diff, ans);
    mergeSort(arr, m + 1, r, diff, ans);
    merge(arr, l, m, r, diff, ans);
  }

  void merge(vector<int>& arr, int l, int m, int r, int diff, long& ans) {
    const int lo = m + 1;
    int hi = m + 1;  // the first index s.t. arr[i] <= arr[hi] + diff

    // For each index i in the range [l, m], add `r - hi + 1` to `ans`.
    for (int i = l; i <= m; ++i) {
      while (hi <= r && arr[i] > arr[hi] + diff)
        ++hi;
      ans += r - hi + 1;
    }

    vector<int> sorted(r - l + 1);
    int k = 0;      // sorted's index
    int i = l;      // left's index
    int j = m + 1;  // right's index

    while (i <= m && j <= r)
      if (arr[i] < arr[j])
        sorted[k++] = arr[i++];
      else
        sorted[k++] = arr[j++];

    // Put the possible remaining left part into the sorted array.
    while (i <= m)
      sorted[k++] = arr[i++];

    // Put the possible remaining right part into the sorted array.
    while (j <= r)
      sorted[k++] = arr[j++];

    copy(sorted.begin(), sorted.end(), arr.begin() + l);
  }
};
/* code provided by PROGIEZ */