Valid Pairs

Easy

0/40

4 upvotes

Asked in company

Problem statement

You are given two integer arrays, 'a' and 'b', both of size 'n'.

A pair (a[i], b[j]) is considered a valid pair if the element from array 'a' is strictly greater than the element from array 'b', i.e., a[i] > b[j].

Your task is to find the maximum number of valid pairs you can form. Each element from both arrays can be used in at most one pair.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'n', representing the size of both arrays.

The second line contains 'n' space-separated integers, representing the elements of array 'a'.

The third line contains 'n' space-separated integers, representing the elements of array 'b'.

Output Format:

Print a single integer, which is the maximum number of valid pairs that can be formed.

Note:

An element from array 'a' and an element from array 'b' can be part of only one pair. Once used, they cannot be used again to form another pair.

Sample Input 1:

3
10 20 30
5 15 25

Sample Output 1:

Explanation for Sample 1:

We can form the following three pairs:
1. (10, 5) since 10 > 5
2. (20, 15) since 20 > 15
3. (30, 25) since 30 > 25
All elements are used, and we have a total of 3 pairs, which is the maximum possible.

Sample Input 2:

4
1 2 8 9
3 4 5 6

Sample Output 2:

Explanation for Sample 2:

The optimal way to form pairs is:
1. (8, 3) since 8 > 3
2. (9, 4) since 9 > 4
The elements 1 and 2 from array 'a' cannot be paired with any remaining elements from array 'b' (5 and 6). The maximum number of pairs is 2.

Expected Time Complexity:

The expected time complexity is O(n log n).

Constraints:

1 <= n <= 10^5
-10^9 <= a[i], b[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Valid Pairs

Time Complexity

The expected time complexity is O(n log n).

Space Complexity

(100% EXP penalty)

Valid Pairs

Console