Given two sorted arrays A[] and B[] of size N, the task is to check if it is possible to merge two given sorted arrays into a new sorted array such that no two consecutive elements are from the same array.
Examples:
Input: A[] = {3, 5, 8}, B[] = {2, 4, 6}
Output: YesExplanation: Merged array = {B[0], A[0], B[1], A[1], B[2], A[2]}
Since the resultant array is sorted array, the required output is Yes.Input: A[] = {12, 4, 2, 5, 3}, B[] = {32, 13, 43, 10, 8}
Output: No
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say flag = true to check if it is possible to form a new sorted array by merging the given two sorted arrays such that no two consecutive elements are from the same array.
- Initialize a variable, say prev to check if the previous element of the merge array are from the array A[] or the array B[]. If prev == 1 then the previous element are from the array A[] and if prev == 0 then the previous element are from the array B[].
- Traverse both the array using variables, i and j and check the following conditions:
- If A[i] < B[j] and prev != 0 then increment the value of i and update the value of prev to 0.
- If B[j] < A[i[ and prev != 1 then increment the value of j and update the value of prev to 1.
- If A[i] == B[j] and prev != 1 then increment the value of j and update the value of prev to 1.
- If A[i] == B[j] and prev != 0 then increment the value of i and update the value of prev to 0.
- If none of the above condition satisfy then update flag = false.
- Finally, print the value of flag.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible to merge// the two given arrays with given conditionsbool checkIfPossibleMerge(int A[], int B[], int N){ // Stores index of // the array A[] int i = 0; // Stores index of // the array B[] int j = 0; // Check if the previous element are from // the array A[] or from the array B[] int prev = -1; // Check if it is possible to merge the two // given sorted arrays with given conditions int flag = 1; // Traverse both the arrays while (i < N && j < N) { // If A[i] is less than B[j] and // previous element are not from A[] if (A[i] < B[j] && prev != 0) { // Update prev prev = 0; // Update i i++; } // If B[j] is less than A[i] and // previous element are not from B[] else if (B[j] < A[i] && prev != 1) { // Update prev prev = 1; // Update j j++; } // If A[i] equal to B[j] else if (A[i] == B[j]) { // If previous element // are not from B[] if (prev != 1) { // Update prev prev = 1; // Update j j++; } // If previous element is // not from A[] else { // Update prev prev = 0; // Update i i++; } } // If it is not possible to merge two // sorted arrays with given conditions else { // Update flag flag = 0; break; } } return flag;}// Driver Codeint main(){ int A[3] = { 3, 5, 8 }; int B[3] = { 2, 4, 6 }; int N = sizeof(A) / sizeof(A[0]); if (checkIfPossibleMerge(A, B, N)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to check if it is possible to merge// the two given arrays with given conditionsstatic boolean checkIfPossibleMerge(int[] A, int[] B, int N){ // Stores index of // the array A[] int i = 0; // Stores index of // the array B[] int j = 0; // Check if the previous element are from // the array A[] or from the array B[] int prev = -1; // Check if it is possible to merge the two // given sorted arrays with given conditions boolean flag = true; // Traverse both the arrays while (i < N && j < N) { // If A[i] is less than B[j] and // previous element are not from A[] if (A[i] < B[j] && prev != 0) { // Update prev prev = 0; // Update i i++; } // If B[j] is less than A[i] and // previous element are not from B[] else if (B[j] < A[i] && prev != 1) { // Update prev prev = 1; // Update j j++; } // If A[i] equal to B[j] else if (A[i] == B[j]) { // If previous element // are not from B[] if (prev != 1) { // Update prev prev = 1; // Update j j++; } // If previous element is // not from A[] else { // Update prev prev = 0; // Update i i++; } } // If it is not possible to merge two // sorted arrays with given conditions else { // Update flag flag = false; break; } } return flag;}// Driver Codepublic static void main(String[] args){ int[] A = { 3, 5, 8 }; int[] B = { 2, 4, 6 }; int N = A.length; if (checkIfPossibleMerge(A, B, N)) { System.out.println("Yes"); } else { System.out.println("No"); }}}// This code is contributed by akhilsaini |
Python3
# Python3 program to implement# the above approach# Function to check if it is possible # to merge the two given arrays with # given conditionsdef checkIfPossibleMerge(A, B, N): # Stores index of # the array A[] i = 0 # Stores index of # the array B[] j = 0 # Check if the previous element # are from the array A[] or from # the array B[] prev = -1 # Check if it is possible to merge # the two given sorted arrays with # given conditions flag = 1 # Traverse both the arrays while (i < N and j < N): # If A[i] is less than B[j] and # previous element are not from A[] if (A[i] < B[j] and prev != 0): # Update prev prev = 0 # Update i i += 1 # If B[j] is less than A[i] and # previous element are not from B[] elif (B[j] < A[i] and prev != 1): # Update prev prev = 1 # Update j j += 1 # If A[i] equal to B[j] elif (A[i] == B[j]): # If previous element # are not from B[] if (prev != 1): # Update prev prev = 1 # Update j j += 1 # If previous element is # not from A[] else: # Update prev prev = 0 # Update i i += 1 # If it is not possible to merge two # sorted arrays with given conditions else: # Update flag flag = 0 break return flag# Driver Codeif __name__ == '__main__': A = [ 3, 5, 8 ] B = [ 2, 4, 6 ] N = len(A) if (checkIfPossibleMerge(A, B, N)): print("Yes") else: print("No")# This code is contributed by akhilsaini |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to check if it is possible to merge// the two given arrays with given conditionsstatic bool checkIfPossibleMerge(int[] A, int[] B, int N){ // Stores index of // the array A[] int i = 0; // Stores index of // the array B[] int j = 0; // Check if the previous element are // from the array A[] or from the // array B[] int prev = -1; // Check if it is possible to merge // the two given sorted arrays with // given conditions bool flag = true; // Traverse both the arrays while (i < N && j < N) { // If A[i] is less than B[j] and // previous element are not from A[] if (A[i] < B[j] && prev != 0) { // Update prev prev = 0; // Update i i++; } // If B[j] is less than A[i] and // previous element are not from B[] else if (B[j] < A[i] && prev != 1) { // Update prev prev = 1; // Update j j++; } // If A[i] equal to B[j] else if (A[i] == B[j]) { // If previous element // are not from B[] if (prev != 1) { // Update prev prev = 1; // Update j j++; } // If previous element is // not from A[] else { // Update prev prev = 0; // Update i i++; } } // If it is not possible to merge two // sorted arrays with given conditions else { // Update flag flag = false; break; } } return flag;}// Driver Codepublic static void Main(){ int[] A = { 3, 5, 8 }; int[] B = { 2, 4, 6 }; int N = A.Length; if (checkIfPossibleMerge(A, B, N)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); }}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to implement// the above approach// Function to check if it is possible to merge// the two given arrays with given conditionsfunction checkIfPossibleMerge(A, B, N){ // Stores index of // the array A[] let i = 0; // Stores index of // the array B[] let j = 0; // Check if the previous element are from // the array A[] or from the array B[] let prev = -1; // Check if it is possible to merge the two // given sorted arrays with given conditions let flag = true; // Traverse both the arrays while (i < N && j < N) { // If A[i] is less than B[j] and // previous element are not from A[] if (A[i] < B[j] && prev != 0) { // Update prev prev = 0; // Update i i++; } // If B[j] is less than A[i] and // previous element are not from B[] else if (B[j] < A[i] && prev != 1) { // Update prev prev = 1; // Update j j++; } // If A[i] equal to B[j] else if (A[i] == B[j]) { // If previous element // are not from B[] if (prev != 1) { // Update prev prev = 1; // Update j j++; } // If previous element is // not from A[] else { // Update prev prev = 0; // Update i i++; } } // If it is not possible to merge two // sorted arrays with given conditions else { // Update flag flag = false; break; } } return flag;} // Driver Code let A = [ 3, 5, 8 ]; let B = [ 2, 4, 6 ]; let N = A.length; if (checkIfPossibleMerge(A, B, N)) { document.write("Yes"); } else { document.write("No"); }// This code is contributed by splevel62.</script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 2: Dynamic Programming:
The given problem can be solved using a dynamic programming approach. We can create a 2D boolean table dp[][] of size (N+1)x(N+1) where dp[i][j] represents if it is possible to merge the first i elements of array A and the first j elements of array B with given conditions.
- The base case is dp[0][0] = true, as we can merge 0 elements from both arrays.
- For each (i,j) such that i>0 and j>0, we can calculate dp[i][j] as follows:
- If A[i-1] == B[j-1], then we can merge both the elements into the resulting array, and the previous element can be from either array. So, dp[i][j] = dp[i-1][j-1].
- If A[i-1] < B[j-1], then we can only merge the element A[i-1] into the resulting array if the previous element is from array B. So, dp[i][j] = dp[i][j-1].
- If A[i-1] > B[j-1], then we can only merge the element B[j-1] into the resulting array if the previous element is from array A. So, dp[i][j] = dp[i-1][j].
Finally, the answer is dp[N][N]. If dp[N][N] is true, it means it is possible to merge the entire arrays A and B with given conditions.
C++
#include <bits/stdc++.h>using namespace std;// Function to check if it is possible to merge// the two given arrays with given conditionsbool checkIfPossibleMerge(int A[], int B[], int N){ // Create a 2D boolean table bool dp[N+1][N+1]; // Base case dp[0][0] = true; // Initialize the first row and column for (int i = 1; i <= N; i++) { dp[i][0] = (A[i-1] > A[i-2]) && dp[i-1][0]; dp[0][i] = (B[i-1] > B[i-2]) && dp[0][i-1]; } // Fill the remaining table for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (A[i-1] == B[j-1]) { dp[i][j] = dp[i-1][j-1]; } else if (A[i-1] < B[j-1]) { dp[i][j] = dp[i][j-1] && (A[i-1] > B[j-2]); } else { dp[i][j] = dp[i-1][j] && (B[j-1] > A[i-2]); } } } return dp[N][N];}// Driver Codeint main(){ int A[3] = { 3, 5, 8 }; int B[3] = { 2, 4, 6 }; int N = sizeof(A) / sizeof(A[0]); if (checkIfPossibleMerge(A, B, N)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
public class MergeArrays { // Function to check if it is possible to merge // the two given arrays with given conditions static boolean checkIfPossibleMerge(int[] A, int[] B, int N) { // Create a 2D boolean table boolean[][] dp = new boolean[N + 1][N + 1]; // Base case dp[0][0] = true; // Initialize the first row and column for (int i = 1; i <= N; i++) { dp[i][0] = (A[i - 1] > A[i - 2]) && dp[i - 1][0]; dp[0][i] = (B[i - 1] > B[i - 2]) && dp[0][i - 1]; } // Fill the remaining table for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else if (A[i - 1] < B[j - 1]) { dp[i][j] = dp[i][j - 1] && (A[i - 1] > B[j - 2]); } else { dp[i][j] = dp[i - 1][j] && (B[j - 1] > A[i - 2]); } } } return dp[N][N]; } // Driver Code public static void main(String[] args) { int[] A = {3, 5, 8}; int[] B = {2, 4, 6}; int N = A.length; if (checkIfPossibleMerge(A, B, N)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
def checkIfPossibleMerge(A, B, N): # Create a 2D boolean table dp = [[False]*(N+1) for _ in range(N+1)] # Base case dp[0][0] = True # Initialize the first row and column for i in range(1, N+1): dp[i][0] = (A[i-1] > A[i-2]) and dp[i-1][0] dp[0][i] = (B[i-1] > B[i-2]) and dp[0][i-1] # Fill the remaining table for i in range(1, N+1): for j in range(1, N+1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] elif A[i-1] < B[j-1]: dp[i][j] = dp[i][j-1] and (A[i-1] > B[j-2]) else: dp[i][j] = dp[i-1][j] and (B[j-1] > A[i-2]) return dp[N][N]# Driver Codeif __name__ == '__main__': A = [3, 5, 8] B = [2, 4, 6] N = len(A) if checkIfPossibleMerge(A, B, N): print("No") else: print("Yes") |
C#
using System;class Program{ // Function to check if it is possible to merge // the two given arrays with given conditions static bool CheckIfPossibleMerge(int[] A, int[] B, int N) { // Create a 2D boolean table bool[,] dp = new bool[N + 1, N + 1]; // Base case dp[0, 0] = true; // Initialize the first row and column for (int i = 1; i <= N; i++) { dp[i, 0] = (i > 1) && (A[i - 1] > A[i - 2]) && dp[i - 1, 0]; dp[0, i] = (i > 1) && (B[i - 1] > B[i - 2]) && dp[0, i - 1]; } // Fill the remaining table for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (A[i - 1] == B[j - 1]) { dp[i, j] = dp[i - 1, j - 1]; } else if (A[i - 1] < B[j - 1]) { dp[i, j] = dp[i, j - 1] && (A[i - 1] > B[j - 2]); } else { dp[i, j] = dp[i - 1, j] && (B[j - 1] > A[i - 2]); } } } return dp[N, N]; } // Driver Code static void Main() { int[] A = { 3, 5, 8 }; int[] B = { 2, 4, 6 }; int N = A.Length; if (CheckIfPossibleMerge(A, B, N)) { Console.WriteLine("No"); } else { Console.WriteLine("Yes"); } }} |
Javascript
function checkIfPossibleMerge(A, B, N) { // Create a 2D boolean table let dp = new Array(N + 1).fill(false).map(() => new Array(N + 1).fill(false)); // Base case dp[0][0] = true; // Initialize the first row and column for (let i = 1; i <= N; i++) { dp[i][0] = (A[i - 1] > A[i - 2]) && dp[i - 1][0]; dp[0][i] = (B[i - 1] > B[i - 2]) && dp[0][i - 1]; } // Fill the remaining table for (let i = 1; i <= N; i++) { for (let j = 1; j <= N; j++) { if (A[i - 1] === B[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else if (A[i - 1] < B[j - 1]) { dp[i][j] = dp[i][j - 1] && (A[i - 1] > B[j - 2]); } else { dp[i][j] = dp[i - 1][j] && (B[j - 1] > A[i - 2]); } } } return dp[N][N];}// Driver Codelet A = [3, 5, 8];let B = [2, 4, 6];let N = A.length;if (checkIfPossibleMerge(A, B, N)) { console.log("No");} else { console.log("Yes");} |
Output
Yes
Time Complexity: O(N^2)
Auxiliary Space: O(N)
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!
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/check-if-two-sorted-arrays-can-be-merged-to-form-a-sorted-array-with-no-adjacent-pair-from-the-same-array/ […]