Given two arrays A and B of the same size N. Check whether array A can be fit into array B. An array is said to fit into another array if by arranging the elements of both arrays, there exists a solution such that the ith element of the first array is less than or equal to ith element of the second array.
Examples:
Input : A[] = { 7, 5, 3, 2 }, B[] = { 5, 4, 8, 7 }
Output : YES
Rearrange the first array to {3, 2, 7, 5}
Do not rearrange the second array's element.
After rearranging, all Ai<=Bi.
Input : A[] = { 7, 5, 3, 2, 5, 105, 45, 10 }, B[] = { 2, 4, 0, 5, 6, 9, 75, 84 }
Output : NO
Approach: Sort both the arrays and check whether Ai is less than or equal to Bi for all 0 ≤ i ≤ N. If at any ith position Ai is greater than Bi return false, otherwise return true.
Steps to solve the problem:
- Sort array A in non-decreasing order.
- Sort array B in non-decreasing order.
- For each element i from 0 to N-1 do the following:
- If A[i] > B[i], return false.
- If the loop completes without returning false, return true.
Below is the implementation of the above approach:
C++
// C++ Program to check whether an array// can be fit into another array with given// condition.#include <bits/stdc++.h>using namespace std;// Returns true if the array A can be fit into// array B, otherwise falsebool checkFittingArrays(int A[], int B[], int N){ // Sort both the arrays sort(A, A + N); sort(B, B + N); // Iterate over the loop and check whether every // array element of A is less than or equal to // its corresponding array element of B for (int i = 0; i < N; i++) if (A[i] > B[i]) return false; return true;}// Driver Codeint main(){ int A[] = { 7, 5, 3, 2 }; int B[] = { 5, 4, 8, 7 }; int N = sizeof(A) / sizeof(A[0]); if (checkFittingArrays(A, B, N)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java Program to check// whether an array can// be fit into another// array with given// condition.import java.io.*;import java.util.*;import java.lang.*;class GFG {// Returns true if the// array A can be fit // into array B, // otherwise falsestatic boolean checkFittingArrays(int []A, int []B, int N){ // Sort both the arrays Arrays.sort(A); Arrays.sort(B); // Iterate over the loop // and check whether every // array element of A is // less than or equal to // its corresponding array // element of B for (int i = 0; i < N; i++) if (A[i] > B[i]) return false; return true;}// Driver Codepublic static void main(String[] args){ int A[] = {7, 5, 3, 2}; int B[] = {5, 4, 8, 7}; int N = A.length; if (checkFittingArrays(A, B, N)) System.out.print("YES"); else System.out.print("NO");}} |
Python3
# Python3 Program to check whether an array# can be fit into another array with given# condition.# Returns true if the array A can be fit into# array B, otherwise falsedef checkFittingArrays(A, B, N): # Sort both the arrays A = sorted(A) B = sorted(B) # Iterate over the loop and check whether # every array element of A is less than # or equal to its corresponding array # element of B for i in range(N): if (A[i] > B[i]): return False return True# Driver CodeA = [7, 5, 3, 2]B = [5, 4, 8, 7]N = len(A)if (checkFittingArrays(A, B, N)): print("YES")else: print("NO")# This code is contributed # by mohit kumar |
C#
// C# Program to check// whether an array can// be fit into another// array with given// condition.using System;class GFG {// Returns true if the// array A can be fit // into array B, // otherwise falsestatic bool checkFittingArrays(int []A, int []B, int N){ // Sort both the arrays Array.Sort(A); Array.Sort(B); // Iterate over the loop // and check whether every // array element of A is // less than or equal to // its corresponding array // element of B for (int i = 0; i < N; i++) if (A[i] > B[i]) return false; return true;}// Driver Codepublic static void Main () { int []A = {7, 5, 3, 2}; int []B = {5, 4, 8, 7}; int N = A.Length; if (checkFittingArrays(A, B, N)) Console.WriteLine("YES"); else Console.WriteLine("NO");}}// This code is contributed // by anuj_67. |
PHP
<?php// PHP Program to check whether an // array can be fit into another // array with given condition.// Returns true if the array A can // be fit into array B, otherwise falsefunction checkFittingArrays($A, $B, $N){ // Sort both the arrays sort($A); sort($B); // Iterate over the loop and check // whether every array element of // A is less than or equal to its // corresponding array element of B for ($i = 0; $i < $N; $i++) if ($A[$i] > $B[$i]) return false; return true;}// Driver Code$A = array( 7, 5, 3, 2 );$B = array( 5, 4, 8, 7 );$N = count($A);if (checkFittingArrays($A, $B, $N)) echo "YES";else echo "NO"; // This code is contributed by shs?> |
Javascript
<script>// Javascript Program to check// whether an array can// be fit into another// array with given// condition. // Returns true if the// array A can be fit // into array B, // otherwise false function checkFittingArrays(A, B, N) { // Sort both the arrays A.sort(function(a, b){return a - b;}); B.sort(function(a, b){return a - b;}); // Iterate over the loop // and check whether every // array element of A is // less than or equal to // its corresponding array // element of B for (let i = 0; i < N; i++) if (A[i] > B[i]) return false; return true; } // Driver Code let A = [7, 5, 3, 2]; let B = [5, 4, 8, 7]; let N = A.length; if (checkFittingArrays(A, B, N)) document.write("YES"); else document.write("NO"); // This code is contributed by unknown2108</script> |
Output
YES
Time Complexity: O(N * logN), where N is the size of the array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
