FastPrepMaximum Bounded One-to-One Pairs
Problem · Array

Maximum Bounded One-to-One Pairs

Learn this problem
● MediumIBM logoIBMNEW GRADOA
See IBM hiring insights

Problem statement

You are given two nonempty integer arrays arr1 and arr2, and a positive integer d.

Form as many one-to-one pairs (a, b) as possible, where a is an unused element of arr1, b is an unused element of arr2, and a <= b <= a + d.

Return the maximum number of valid pairs. The input arrays do not need to be sorted.

Function

maxValidPairs(arr1: int[], arr2: int[], d: int) → int

Examples

Example 1

arr1 = [8,20,35,45]arr2 = [25,50]d = 10return = 2

Pair 20 with 25 and 45 with 50. Both satisfy the inclusive bounds.

Example 2

arr1 = [5,1,3]arr2 = [3,6,2]d = 1return = 3

After sorting, use the pairs (1,2), (3,3), and (5,6).

Example 3

arr1 = [1,2,3]arr2 = [10,11]d = 2return = 0

Every value in arr2 exceeds the upper bound of every possible pair.

Constraints

  • 1 <= arr1.length, arr2.length <= 10^5
  • 0 <= arr1[i], arr2[i] <= 10^9
  • 1 <= d <= 10^5

More IBM problems

drafts saved locally
public int maxValidPairs(int[] arr1, int[] arr2, int d) {
    // write your code here
}
arr1[8,20,35,45]
arr2[25,50]
d10
expected2
checking account