Sorting: Check if the array can be fit into another array by re-arranging the elements.

You are given 2 arrays of same size.

You need check if there exist a solution such that the ith element of the first array is less than or equal to ith element of the second array by re arranging the elements of the first array.

Input:

A = [8, 7, 5, 1]

B = [2, 6, 8, 10]

You can re arrange the array into [1, 5, 7, 8], this will solve the issue.

Output: Yes

Sort both the arrays in ascending order.

Iterate both of the arrays and check if A[i] > B[i] return false.

Else return true.

Time Complexity: O(n log n)

Space Complexity: O(1)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;


bool solution(int A[], int B[], int N)
{
	sort(A, A + N);
	sort(B, B + N);

	for (int i = 0; i < N; i++)
		if (A[i] > B[i])
			return false;

	return true;
}

int main()
{
	int A[] = { 8, 7, 5, 1 };
	int B[] = { 2, 6, 8, 10 };
	int N = sizeof(A) / sizeof(A[0]);

	if (solution(A, B, N))
		cout << "YES";
	else
		cout << "NO";
	return 0;
}

Output

Yes