Given two integer arrays arr[] and brr[] consisting of distinct elements of size N and M respectively and an integer K, the task is to find the count of pairs (arr[i], brr[j]) such that (brr[j] – arr[i]) > K.
Examples:
Input: arr[] = {5, 9, 1, 8}, brr[] = {10, 12, 7, 4, 2, 3}, K = 3
Output: 6
Explanation:
Possible pairs that satisfy the given conditions are: {(5, 10), (5, 12), (1, 10), (1, 12), (1, 7), (8, 12)}.
Therefore, the required output is 6.Input: arr[] = {2, 10}, brr[] = {5, 7}, K = 2
Output: 2
Explanation:
Possible pairs that satisfy the given conditions are: {(2, 5), (2, 7)}.
Therefore, the required output is 2.
Naive Approach: Refer to the previous post of this article for the simplest approach to solve this problem.
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Two Pointer Approach: Refer to the previous post of this article for the two pointer solution to this problem.
Time Complexity: O(N * log(N) + M * log(M))
Auxiliary Space: O(1)
Efficient Approach: The idea is to sort the smaller array and traverse through the larger array for each element, find the appropriate element in the smaller array for pairing using Binary Search. Follow the steps below to solve the problem:
- Initialize a variable count to store the count of pairs.
- If arr[] size is smaller than brr[], then do the following.
- Sort the array arr[] and traverse the array brr[].
- Find the lower bound of (brr[j] – k) in arr[] since the numbers which are less than brr[j] – k in arr[] will perfectly make pair with brr[j].
- Add the lower bound index with the count.
- If brr[] size is smaller than arr[], then do the following.
- Sort the array brr[] and traverse through arr[].
- Find the upper bound of (arr[i] + k) in brr[] since the numbers which are greater than arr[i]+k in brr[] will perfectly make pair with arr[i].
- Add (Size of brr[] – upper bound index) with the count.
- After the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs that satisfy// the given conditionsint countPairs(int v1[], int v2[], int n, int m, int k){ // Stores the count of pairs int count = 0; // If v1[] is smaller than v2[] if (n <= m) { // Sort the array v1[] sort(v1, v1 + n); // Traverse the array v2[] for (int j = 0; j < m; j++) { // Returns the address of // the first number which // is >= v2[j] - k int index = lower_bound(v1, v1 + n, v2[j] - k) - v1; // Increase the count by all // numbers less than v2[j] - k count += index; } } // Otherwise else { // Sort the array v2[] sort(v2, v2 + m); // Traverse the array v1[] for (int i = 0; i < n; i++) { // Returns the address of // the first number which // is > v1[i] + k int index = upper_bound(v2, v2 + m, v1[i] + k) - v2; // Increase the count by all // numbers greater than v1[i] + k count += m - index; } } // Return the total count of pairs return count;}// Driver Codeint main(){ int arr[] = { 5, 9, 1, 8 }; int brr[] = { 10, 12, 7, 4, 2, 3 }; int K = 3; int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(brr) / sizeof(brr[0]); cout << countPairs(arr, brr, N, M, K); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{// Function to count pairs // that satisfy the given // conditionsstatic int countPairs(int v1[], int v2[], int n, int m, int k){ // Stores the count of pairs int count = 0; // If v1[] is smaller than v2[] if (n <= m) { // Sort the array v1[] Arrays.sort(v1); // Traverse the array v2[] for (int j = 0; j < m; j++) { // Returns the address of // the first number which // is >= v2[j] - k int index = lowerBound(v1, 0, n, v2[j] - k); // Increase the count by all // numbers less than v2[j] - k count += index; } } // Otherwise else { // Sort the array v2[] Arrays.sort(v2); // Traverse the array v1[] for (int i = 0; i < n; i++) { // Returns the address of // the first number which // is > v1[i] + k int index = upperBound(v2, 0, m, v1[i] + k); // Increase the count by all // numbers greater than v1[i] + k count += m - index; } } // Return the total count of pairs return count;}static int lowerBound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;}static int upperBound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(a[middle] > element) high = middle; else low = middle + 1; } return low;} // Driver Codepublic static void main(String[] args){ int arr[] = {5, 9, 1, 8}; int brr[] = {10, 12, 7, 4, 2, 3}; int K = 3; int N = arr.length; int M = brr.length; System.out.print(countPairs(arr, brr, N, M, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approachfrom bisect import bisect_left, bisect_right# Function to count pairs that satisfy# the given conditionsdef countPairs(v1, v2, n, m, k): # Stores the count of pairs count = 0 # If v1[] is smaller than v2[] if (n <= m): # Sort the array v1[] v1 = sorted(v1) # Traverse the array v2[] for j in range(m): # Returns the address of # the first number which # is >= v2[j] - k index = bisect_left(v1, v2[j] - k) # Increase the count by all # numbers less than v2[j] - k count += index # Otherwise else: # Sort the array v2[] v2 = sorted(v2) # Traverse the array v1[] for i in range(n): # Returns the address of # the first number which # is > v1[i] + k index = bisect_right(v2, v1[i] + k) # Increase the count by all # numbers greater than v1[i] + k count += m - index # Return the total count of pairs return count# Driver Codeif __name__ == '__main__': arr = [ 5, 9, 1, 8 ] brr = [ 10, 12, 7, 4, 2, 3] K = 3 N = len(arr) M = len(brr) print(countPairs(arr, brr, N, M, K))# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;class GFG{// Function to count pairs // that satisfy the given // conditionsstatic int countPairs(int []v1, int []v2, int n, int m, int k){ // Stores the count of pairs int count = 0; // If v1[] is smaller than v2[] if (n <= m) { // Sort the array v1[] Array.Sort(v1); // Traverse the array v2[] for (int j = 0; j < m; j++) { // Returns the address of // the first number which // is >= v2[j] - k int index = lowerBound(v1, 0, n, v2[j] - k); // Increase the count by all // numbers less than v2[j] - k count += index; } } // Otherwise else { // Sort the array v2[] Array.Sort(v2); // Traverse the array v1[] for (int i = 0; i < n; i++) { // Returns the address of // the first number which // is > v1[i] + k int index = upperBound(v2, 0, m, v1[i] + k); // Increase the count by all // numbers greater than v1[i] + k count += m - index; } } // Return the total count // of pairs return count;}static int lowerBound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;}static int upperBound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(a[middle] > element) high = middle; else low = middle + 1; } return low;} // Driver Codepublic static void Main(String[] args){ int []arr = {5, 9, 1, 8}; int []brr = {10, 12, 7, 4, 2, 3}; int K = 3; int N = arr.Length; int M = brr.Length; Console.Write(countPairs(arr, brr, N, M, K));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to count pairs// that satisfy the given// conditionsfunction countPairs(v1, v2, n, m, k){ // Stores the count of pairs let count = 0; // If v1[] is smaller than v2[] if (n <= m) { // Sort the array v1[] v1.sort(); // Traverse the array v2[] for (let j = 0; j < m; j++) { // Returns the address of // the first number which // is >= v2[j] - k let index = lowerBound(v1, 0, n, v2[j] - k); // Increase the count by all // numbers less than v2[j] - k count += index; } } // Otherwise else { // Sort the array v2[] v2.sort(); // Traverse the array v1[] for (let i = 0; i < n; i++) { // Returns the address of // the first number which // is > v1[i] + k let index = upperBound(v2, 0, m, v1[i] + k); // Increase the count by all // numbers greater than v1[i] + k count += m - index; } } // Return the total count of pairs return count;} function lowerBound(a, low, high, element){ while(low < high) { let middle = low + (high - low) / 2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;} function upperBound(a, low, high, element){ while(low < high) { let middle = low + (high - low) / 2; if(a[middle] > element) high = middle; else low = middle + 1; } return low;}// Driver Code let arr = [5, 9, 1, 8]; let brr = [10, 12, 7, 4, 2, 3]; let K = 3; let N = arr.length; let M = brr.length; document.write(countPairs(arr, brr, N, M, K)); </script> |
Output:
6
Time Complexity: O((N+M) * min(log(N), log(M)))
Auxiliary Space: O(1)
