Find if new Array can be formed from given two Arrays.
Given two arrays arr1[] and arr2[] each of size N, the task is to create another array of size N from these two arrays by choosing i’th element of the new array from either arr1[i] or arr2[i] and the difference between any adjacent elements of the new array is less than or equal to K. If this is possible print “Yes” otherwise “No“.
Examples:
Input: arr1[] = {9, 8, 3, 7, 2}, arr2[] = {1, 6, 2, 9, 5}, K = 4
Output: Yes
Explanation: A new array can be {9, 6, 3, 7, 5} Where, 9 is taken from the first array, 6 is taken from the second array, 3 is taken from the first array, 7 is taken from the first array and finally 5 is taken from the second array. The difference between adjacent elements is less than equal to K.Input: arr1[] = {1 1 1 100}, arr2[] = {1 2 3 100}, K = 90
Output: No
Naive Approach: The article can be solved based on the following idea:
The Basic way to solve this is to generate all possible combinations by using recursive brute force.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve the following problem efficiently.
- dp[i][j] represents either true or false, a new array formed till the size i with last element picked from the j’th array.
- It can be observed that there are N * 2 states but the recursive function is called 2N times.
- That means that some states are called repeatedly. So the idea is to store the value of states. This can be done using a recursive structure intact and just storing the value in an array or HashMap and whenever the function is called, return the value stored without computing.
Follow the steps below to solve the problem:
- Create a recursive function that takes two parameters i and j. new array formed till i’th index with the last element picked from array j.
- Call recursive function for both taking element from the first array and taking an element from the second array.
- Check the base case if all N elements are selected return 1.
- Create a 2d array of dp[200001][3] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the code implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Dp table initialized with - 1 int dp[200001][3]; // Recursive function to tell whether new // array can be formed from given // two arrays int recur( int i, int j, int k, int arr1[], int arr2[], int N) { // Base case if (i == N) { // Return 1 as the creation of // new array of size N is possible return 1; } // If current state is precomputed then // just return already computed value if (dp[i][j + 1] != -1) return dp[i][j + 1]; // Answer initialized with considering // no possibility int ans = 0; // First element to be chosen if (j == -1) { // Taking first element from arr1[] ans = recur(i + 1, 0, k, arr1, arr2, N); // Taking first element from arr2[] ans = max(ans, recur(i + 1, 1, k, arr1, arr2, N)); } // Last element was chosen from // first array else if (j == 0) { // If the absolute difference with // previous element chosen is less // than equal to K then choose arr2[i] if ( abs (arr2[i] - arr1[i - 1]) <= k) ans = recur(i + 1, 1, k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less than // equal to K then choose arr1[i] if ( abs (arr1[i] - arr1[i - 1]) <= k) ans = max(ans, recur(i + 1, 0, k, arr1, arr2, N)); } // Last element was chosen from // second array else { // If the absolute difference with // previous element chosen is less than // equal to K then choose arr2[i] if ( abs (arr2[i] - arr2[i - 1]) <= k) ans = recur(i + 1, 1, k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less // than equal to K then choose arr1[i] if ( abs (arr1[i] - arr2[i - 1]) <= k) ans = max(ans, recur(i + 1, 0, k, arr1, arr2, N)); } // Save and return dp value return dp[i][j + 1] = ans; } // Function to find whether new array // can be formed from the given two // arrays void isNewArrayPossible( int arr1[], int arr2[], int N, int K) { // Filling dp table with -1 memset (dp, -1, sizeof (dp)); // If recur function returns one then // it is possible else it is not if (recur(0, -1, K, arr1, arr2, N)) cout << "Yes" << endl; else cout << "No" << endl; } // Driver Code int main() { // Input int arr1[] = { 9, 8, 3, 7, 2 }, arr2[] = { 1, 6, 2, 9, 5 }; int N = sizeof (arr1) / sizeof (arr1[0]); int K = 4; // Function Call isNewArrayPossible(arr1, arr2, N, K); // Input2 int arr3[] = { 1, 1, 1, 100 }, arr4[] = { 1, 2, 3, 100 }; int N1 = sizeof (arr3) / sizeof (arr3[0]); int K1 = 90; // Function call isNewArrayPossible(arr3, arr4, N1, K1); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Dp table initialized with -1 static int [][] dp = new int [ 200001 ][ 3 ]; // Recursive function to tell whether new // array can be formed from given // two arrays static int recur( int i, int j, int k, int [] arr1, int [] arr2, int N) { // Base case if (i == N) { // Return 1 as the creation of // new array of size N is possible return 1 ; } // If current state is precomputed then // just return already computed value if (dp[i][j + 1 ] != - 1 ) return dp[i][j + 1 ]; // Answer initialized with considering // no possibility int ans = 0 ; // First element to be chosen if (j == - 1 ) { // Taking first element from arr1[] ans = recur(i + 1 , 0 , k, arr1, arr2, N); // Taking first element from arr2[] ans = Math.max( ans, recur(i + 1 , 1 , k, arr1, arr2, N)); } // Last element was chosen from // first array else if (j == 0 ) { // If the absolute difference with // previous element chosen is less // than equal to K then choose arr2[i] if (Math.abs(arr2[i] - arr1[i - 1 ]) <= k) ans = recur(i + 1 , 1 , k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less than // equal to K then choose arr1[i] if (Math.abs(arr1[i] - arr1[i - 1 ]) <= k) ans = Math.max( ans, recur(i + 1 , 0 , k, arr1, arr2, N)); } // Last element was chosen from // second array else { // If the absolute difference with // previous element chosen is less than // equal to K then choose arr2[i] if (Math.abs(arr2[i] - arr2[i - 1 ]) <= k) ans = recur(i + 1 , 1 , k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less // than equal to K then choose arr1[i] if (Math.abs(arr1[i] - arr2[i - 1 ]) <= k) ans = Math.max( ans, recur(i + 1 , 0 , k, arr1, arr2, N)); } // Save and return dp value return dp[i][j + 1 ] = ans; } static void isNewArrayPossible( int [] arr1, int [] arr2, int N, int K) { for ( int i = 0 ; i < dp.length; i++) { for ( int j = 0 ; j < dp[ 0 ].length; j++) { dp[i][j] = - 1 ; } } if (recur( 0 , - 1 , K, arr1, arr2, N)== 1 ) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } public static void main(String[] args) { int [] arr1 = { 9 , 8 , 3 , 7 , 2 }, arr2 = { 1 , 6 , 2 , 9 , 5 }; int N = arr1.length; int K = 4 ; isNewArrayPossible(arr1, arr2, N, K); int [] arr3 = { 1 , 1 , 1 , 100 }, arr4 = { 1 , 2 , 3 , 100 }; int N1 = arr3.length; int K1 = 90 ; isNewArrayPossible(arr3, arr4, N1, K1); } } // This code is contributed by lokesh. |
Python3
# Python code to implement the approach # Dp table initialized with -1 dp = [[ - 1 for j in range ( 3 )] for i in range ( 200001 )] def recur(i, j, k, arr1, arr2, N): # Base case if i = = N: # Return 1 as the creation of # new array of size N is possible return 1 # If current state is precomputed then # just return already computed value if dp[i][j + 1 ] ! = - 1 : return dp[i][j + 1 ] # Answer initialized with considering # no possibility ans = 0 # First element to be chosen if j = = - 1 : # Taking first element from arr1[] ans = recur(i + 1 , 0 , k, arr1, arr2, N) # Taking first element from arr2[] ans = max (ans, recur(i + 1 , 1 , k, arr1, arr2, N)) # Last element was chosen from # first array elif j = = 0 : # If the absolute difference with # previous element chosen is less # than equal to K then choose arr2[i] if abs (arr2[i] - arr1[i - 1 ]) < = k: ans = recur(i + 1 , 1 , k, arr1, arr2, N) # If the absolute difference with # previous element chosen is less # than equal to K then choose arr1[i] if abs (arr1[i] - arr1[i - 1 ]) < = k: ans = max (ans, recur(i + 1 , 0 , k, arr1, arr2, N)) # Last element was chosen from # second array else : # If the absolute difference with # previous element chosen is less than # equal to K then choose arr2[i] if abs (arr2[i] - arr2[i - 1 ]) < = k: ans = recur(i + 1 , 1 , k, arr1, arr2, N) # If the absolute difference with # previous element chosen is less # than equal to K then choose arr1[i] if abs (arr1[i] - arr2[i - 1 ]) < = k: ans = max (ans, recur(i + 1 , 0 , k, arr1, arr2, N)) # Save and return dp value dp[i][j + 1 ] = ans return ans def isNewArrayPossible(arr1, arr2, N, K): for i in range ( len (dp)): for j in range ( len (dp[ 0 ])): dp[i][j] = - 1 if recur( 0 , - 1 , K, arr1, arr2, N) = = 1 : print ( "Yes" ) else : print ( "No" ) arr1 = [ 9 , 8 , 3 , 7 , 2 ] arr2 = [ 1 , 6 , 2 , 9 , 5 ] N = len (arr1) K = 4 isNewArrayPossible(arr1, arr2, N, K) arr3 = [ 1 , 1 , 1 , 100 ] arr4 = [ 1 , 2 , 3 , 100 ] N1 = len (arr3) K1 = 90 isNewArrayPossible(arr3, arr4, N1, K1) # This code is contributed by lokesh. |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Dp table initialized with - 1 static int [,] dp = new int [200001, 3]; // Recursive function to tell whether new // array can be formed from given // two arrays static int recur( int i, int j, int k, int [] arr1, int [] arr2, int N) { // Base case if (i == N) { // Return 1 as the creation of // new array of size N is possible return 1; } // If current state is precomputed then // just return already computed value if (dp[i,j + 1] != -1) return dp[i, j + 1]; // Answer initialized with considering // no possibility int ans = 0; // First element to be chosen if (j == -1) { // Taking first element from arr1[] ans = recur(i + 1, 0, k, arr1, arr2, N); // Taking first element from arr2[] ans = Math.Max(ans, recur(i + 1, 1, k, arr1, arr2, N)); } // Last element was chosen from // first array else if (j == 0) { // If the absolute difference with // previous element chosen is less // than equal to K then choose arr2[i] if (Math.Abs(arr2[i] - arr1[i - 1]) <= k) ans = recur(i + 1, 1, k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less than // equal to K then choose arr1[i] if (Math.Abs(arr1[i] - arr1[i - 1]) <= k) ans = Math.Max(ans, recur(i + 1, 0, k, arr1, arr2, N)); } // Last element was chosen from // second array else { // If the absolute difference with // previous element chosen is less than // equal to K then choose arr2[i] if (Math.Abs(arr2[i] - arr2[i - 1]) <= k) ans = recur(i + 1, 1, k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less // than equal to K then choose arr1[i] if (Math.Abs(arr1[i] - arr2[i - 1]) <= k) ans = Math.Max(ans, recur(i + 1, 0, k, arr1, arr2, N)); } // Save and return dp value return dp[i, j + 1] = ans; } // Function to find whether new array // can be formed from the given two // arrays static void isNewArrayPossible( int [] arr1, int [] arr2, int N, int K) { // Filling dp table with -1 for ( int i=0; i<200001; i++) for ( int j=0; j<3; j++) dp[i, j]=-1; // If recur function returns one then // it is possible else it is not if (recur(0, -1, K, arr1, arr2, N)>0) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } // Driver Code public static void Main( string [] args) { // Input int [] arr1 = { 9, 8, 3, 7, 2 }; int [] arr2 = { 1, 6, 2, 9, 5 }; int N = arr1.Length; int K = 4; // Function Call isNewArrayPossible(arr1, arr2, N, K); // Input2 int [] arr3 = { 1, 1, 1, 100 }; int [] arr4 = { 1, 2, 3, 100 }; int N1 = arr3.Length; int K1 = 90; // Function call isNewArrayPossible(arr3, arr4, N1, K1); } } // This code is contributed by ritaagarwal. |
Javascript
// Javascript code to implement the approach // Dp table initialized with - 1 let dp= new Array(200001); for (let i=0; i<200001; i++) dp[i]= new Array(3); function memset(dp, x) { for (let i=0; i<200001; i++) for (let j=0; j<3; j++) dp[i][j]=-1; } // Recursive function to tell whether new // array can be formed from given // two arrays function recur(i, j, k, arr1, arr2, N) { // Base case if (i == N) { // Return 1 as the creation of // new array of size N is possible return 1; } // If current state is precomputed then // just return already computed value if (dp[i][j + 1] != -1) return dp[i][j + 1]; // Answer initialized with considering // no possibility let ans = 0; // First element to be chosen if (j == -1) { // Taking first element from arr1[] ans = recur(i + 1, 0, k, arr1, arr2, N); // Taking first element from arr2[] ans = Math.max(ans, recur(i + 1, 1, k, arr1, arr2, N)); } // Last element was chosen from // first array else if (j == 0) { // If the absolute difference with // previous element chosen is less // than equal to K then choose arr2[i] if (Math.abs(arr2[i] - arr1[i - 1]) <= k) ans = recur(i + 1, 1, k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less than // equal to K then choose arr1[i] if (Math.abs(arr1[i] - arr1[i - 1]) <= k) ans = Math.max(ans, recur(i + 1, 0, k, arr1, arr2, N)); } // Last element was chosen from // second array else { // If the absolute difference with // previous element chosen is less than // equal to K then choose arr2[i] if (Math.abs(arr2[i] - arr2[i - 1]) <= k) ans = recur(i + 1, 1, k, arr1, arr2, N); // If the absolute difference with // previous element chosen is less // than equal to K then choose arr1[i] if (Math.abs(arr1[i] - arr2[i - 1]) <= k) ans = Math.max(ans, recur(i + 1, 0, k, arr1, arr2, N)); } // Save and return dp value return dp[i][j + 1] = ans; } // Function to find whether new array // can be formed from the given two // arrays function isNewArrayPossible(arr1, arr2, N, K) { // Filling dp table with -1 memset(dp, -1); // If recur function returns one then // it is possible else it is not if (recur(0, -1, K, arr1, arr2, N)) console.log( "Yes" ); else console.log( "No" ); } // Driver Code // Input let arr1 = [ 9, 8, 3, 7, 2 ], arr2 = [ 1, 6, 2, 9, 5 ]; let N = arr1.length; let K = 4; // Function Call isNewArrayPossible(arr1, arr2, N, K); // Input2 let arr3 = [ 1, 1, 1, 100 ], arr4 = [ 1, 2, 3, 100 ]; let N1 = arr3.length; let K1 = 90; // Function call isNewArrayPossible(arr3, arr4, N1, K1); // This code is contributed by poojaagarwal2. |
Yes No
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
New Approach Using Binary Search :
- First, sort both arrays arr1 and arr2 in ascending order.
- Initialize two pointers l and r to 0, which will be used to compare elements from arr1 and arr2.
- For each element in the output array, find the minimum and maximum values that can be chosen from arr1 and arr2 such that the absolute difference between adjacent elements in the output array is less than or equal to K. This can be done using binary search on arr1 and arr2.
- If no such element is found, return “No”. Otherwise, add the chosen element to the output array and update the pointers l and r accordingly.
- Repeat step 3 and 4 until all elements in the output array are chosen.
Below is the implementation of the above approach :
C++
#include <algorithm> #include <iostream> #include <vector> using namespace std; string can_create_array(vector< int > arr1, vector< int > arr2, int k) { // Sort both arrays sort(arr1.begin(), arr1.end()); sort(arr2.begin(), arr2.end()); int n = arr1.size(); vector< int > output(n, 0); int l = 0, r = 0; // Fill the output array for ( int i = 0; i < n; i++) { // Find the minimum and maximum values that can be // chosen from arr1 and arr2 int min_val = max(arr1[l] - k, arr2[r] - k); int max_val = min(arr1[l] + k, arr2[r] + k); // Check if there is an element in the range // [min_val, max_val] bool found = false ; for ( int j = l; j < n; j++) { if (arr1[j] > max_val) { break ; } if (arr1[j] >= min_val) { output[i] = arr1[j]; l = j + 1; found = true ; break ; } } if (!found) { for ( int j = r; j < n; j++) { if (arr2[j] > max_val) { return "No" ; } if (arr2[j] >= min_val) { output[i] = arr2[j]; r = j + 1; found = true ; break ; } } } if (!found) { return "No" ; } } return "Yes" ; } int main() { // Test Cases vector< int > arr1 = { 9, 8, 3, 7, 2 }; vector< int > arr2 = { 1, 6, 2, 9, 5 }; int k = 4; cout << can_create_array(arr1, arr2, k) << endl; // Output: Yes arr1 = { 1, 1, 1, 100 }; arr2 = { 1, 2, 3, 100 }; k = 90; cout << can_create_array(arr1, arr2, k) << endl; // Output: No return 0; } // This code is contributed by chinmaya121221 |
Java
import java.util.*; class Main { static String can_create_array(ArrayList<Integer> arr1, ArrayList<Integer> arr2, int k) { // Sort both arrays Collections.sort(arr1); Collections.sort(arr2); int n = arr1.size(); ArrayList<Integer> output = new ArrayList<>(Collections.nCopies(n, 0 )); int l = 0 , r = 0 ; // Fill the output array for ( int i = 0 ; i < n; i++) { // Find the minimum and maximum values that can be // chosen from arr1 and arr2 int min_val = Math.max(arr1.get(l) - k, arr2.get(r) - k); int max_val = Math.min(arr1.get(l) + k, arr2.get(r) + k); // Check if there is an element in the range // [min_val, max_val] boolean found = false ; for ( int j = l; j < n; j++) { if (arr1.get(j) > max_val) { break ; } if (arr1.get(j) >= min_val) { output.set(i, arr1.get(j)); l = j + 1 ; found = true ; break ; } } if (!found) { for ( int j = r; j < n; j++) { if (arr2.get(j) > max_val) { return "No" ; } if (arr2.get(j) >= min_val) { output.set(i, arr2.get(j)); r = j + 1 ; found = true ; break ; } } } if (!found) { return "No" ; } } return "Yes" ; } public static void main(String[] args) { // Test Cases ArrayList<Integer> arr1 = new ArrayList<>(Arrays.asList( 9 , 8 , 3 , 7 , 2 )); ArrayList<Integer> arr2 = new ArrayList<>(Arrays.asList( 1 , 6 , 2 , 9 , 5 )); int k = 4 ; System.out.println(can_create_array(arr1, arr2, k)); // Output: Yes arr1 = new ArrayList<>(Arrays.asList( 1 , 1 , 1 , 100 )); arr2 = new ArrayList<>(Arrays.asList( 1 , 2 , 3 , 100 )); k = 90 ; System.out.println(can_create_array(arr1, arr2, k)); // Output: No } } |
Python3
def can_create_array(arr1, arr2, k): # Sort both arrays arr1.sort() arr2.sort() n = len (arr1) output = [ 0 ] * n l = r = 0 # Fill the output array for i in range (n): # Find the minimum and maximum values that can be chosen from arr1 and arr2 min_val = max (arr1[l] - k, arr2[r] - k) max_val = min (arr1[l] + k, arr2[r] + k) # Check if there is an element in the range [min_val, max_val] found = False for j in range (l, n): if arr1[j] > max_val: break if arr1[j] > = min_val: output[i] = arr1[j] l = j + 1 found = True break if not found: for j in range (r, n): if arr2[j] > max_val: return "No" if arr2[j] > = min_val: output[i] = arr2[j] r = j + 1 found = True break if not found: return "No" return "Yes" # Test Cases arr1 = [ 9 , 8 , 3 , 7 , 2 ] arr2 = [ 1 , 6 , 2 , 9 , 5 ] k = 4 print (can_create_array(arr1, arr2, k)) # Output: Yes arr1 = [ 1 , 1 , 1 , 100 ] arr2 = [ 1 , 2 , 3 , 100 ] k = 90 print (can_create_array(arr1, arr2, k)) # Output: No # This code is Contributed by chinmaya121221 |
C#
using System; using System.Collections.Generic; using System.Linq; class MainClass { static string CanCreateArray(List< int > arr1, List< int > arr2, int k) { // Sort both arrays arr1.Sort(); arr2.Sort(); int n = arr1.Count; List< int > output = new List< int >(Enumerable.Repeat(0, n)); int l = 0, r = 0; // Fill the output array for ( int i = 0; i < n; i++) { // Find the minimum and maximum values that can be // chosen from arr1 and arr2 int min_val = Math.Max(arr1[l] - k, arr2[r] - k); int max_val = Math.Min(arr1[l] + k, arr2[r] + k); // Check if there is an element in the range // [min_val, max_val] bool found = false ; for ( int j = l; j < n; j++) { if (arr1[j] > max_val) { break ; } if (arr1[j] >= min_val) { output[i] = arr1[j]; l = j + 1; found = true ; break ; } } if (!found) { for ( int j = r; j < n; j++) { if (arr2[j] > max_val) { return "No" ; } if (arr2[j] >= min_val) { output[i] = arr2[j]; r = j + 1; found = true ; break ; } } } if (!found) { return "No" ; } } return "Yes" ; } // Driver code public static void Main( string [] args) { // Test Cases List< int > arr1 = new List< int >( new int [] {9, 8, 3, 7, 2}); List< int > arr2 = new List< int >( new int [] {1, 6, 2, 9, 5}); int k = 4; Console.WriteLine(CanCreateArray(arr1, arr2, k)); // Output: Yes arr1 = new List< int >( new int [] {1, 1, 1, 100}); arr2 = new List< int >( new int [] {1, 2, 3, 100}); k = 90; Console.WriteLine(CanCreateArray(arr1, arr2, k)); // Output: No } } |
Javascript
function can_create_array(arr1, arr2, k) { // Sort both arrays arr1.sort((a, b) => a - b); arr2.sort((a, b) => a - b); let n = arr1.length; let output = Array(n).fill(0); let l = 0, r = 0; // Fill the output array for (let i = 0; i < n; i++) { // Find the minimum and maximum values that can be chosen from arr1 and arr2 let min_val = Math.max(arr1[l] - k, arr2[r] - k); let max_val = Math.min(arr1[l] + k, arr2[r] + k); // Check if there is an element in the range [min_val, max_val] let found = false ; for (let j = l; j < n; j++) { if (arr1[j] > max_val) { break ; } if (arr1[j] >= min_val) { output[i] = arr1[j]; l = j + 1; found = true ; break ; } } if (!found) { for (let j = r; j < n; j++) { if (arr2[j] > max_val) { return "No" ; } if (arr2[j] >= min_val) { output[i] = arr2[j]; r = j + 1; found = true ; break ; } } } if (!found) { return "No" ; } } return "Yes" ; } // Test Cases let arr1 = [9, 8, 3, 7, 2]; let arr2 = [1, 6, 2, 9, 5]; let k = 4; console.log(can_create_array(arr1, arr2, k)); // Output: Yes arr1 = [1, 1, 1, 100] arr2 = [1, 2, 3, 100] k = 90 console.log(can_create_array(arr1, arr2, k)) |
Output :
Yes No
Time Complexity : O(n^2), where n is the length of the arrays.
Auxiliary Space : O(n)