Last Updated: 20 Aug, 2025

Valid Pairs

Easy
Asked in company
Amazon

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.


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.