Check if array can be divided into two subsequences merging whom makes Array sorted
Given an integer array A[] of size N, the task is to check if the array can be divided into two subsequences such that appending one of them at the end of the other makes the array sorted.
A sub-sequence is a sequence that can be obtained from the array by deleting some or no elements from it. It may or may not be a continuous part of an array.
Examples:
Input: arr[] = {1, 4, 5, 2, 3, 4}
Output: Yes
Explanation :
First Sub-Sequence (P) : {1, 2, 3, 4};
Second Sub-Sequence (Q) : {4, 5};
Merging both Sub-Sequence Gives Sorted Array:
P+Q = {1, 2, 3, 4} + {4, 5} = {1, 2, 3, 4, 4, 5}Input: arr[] = {1, 4, 6, 3, 5}
Output: No
Approach: The idea behind solving the problem is:
Make a copy of the array and sort the copy. Find two increasing subsequences from the array which match the order of the sorted copy. If the combined elements of both the subsequences form the duplicate of sorted array then such subsequences are possible.
Follow the steps mentioned below to implement the idea:
- Make a temp[] array which stores all the element of input array.
- Sort the temp[] array.
- Iterate twice on unsorted input array and try to find two sorted sub – sequences, having an order same as in temp[] array.
- Merge these two subsequences.
- If the merged array is a duplicate of the temp[] array then the requirement is satisfied.
- If such subsequences are not possible, return “No” as the answer.
Follow the below illustration for a better understanding.
Illustration:
Consider array arr[] = {1, 4, 5, 2, 3, 4};
Thus, temp[] array (sorted of input array): {1, 2, 3, 4, 4, 5};First Iteration (finding first sorted subsequence):
=> We will get elements 1, 2, 3, and 4 which maintains the order as in temp[],
=> Store them in another array: {1, 2, 3, 4}.Second Iteration (finding second sorted subsequence):
=> We will get 4, 5.
=> Now add these elements also in the new array: {1, 2, 3, 4, 4, 5}.2 iterations have been completed.
temp[] = new arraySo the output will be “Yes”.
Below is the implementation of this approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to check if two subsequences exist void solve( int arr1[], int n) { // Temporary array, which will contain // same element and in sorted order // of input array int temp[n]; for ( int i = 0; i < n; i++) { temp[i] = arr1[i]; } sort(temp, temp + n); // Counter to iterate on temp[] array // to find elements in sorted manner. int counter = 0; // New array which will store searched elements // in two iterations. int arr[n]; // Loop for searching twice in input array. for ( int i = 0; i < 2; i++) { // Loop to search for elements in // sorted manner in input array. for ( int j = 0; j < n; j++) { // When element at temp[counter] // and arr1[j] matches. if (arr1[j] == temp[counter]) { // Storing that element in array arr[counter] = arr1[j]; counter++; if (counter == n) { break ; } } } } bool flag = true ; for ( int i = 0; i < n; i++) { if (arr[i] != temp[i]) { flag = false ; break ; } } if (flag == true ) cout << "Yes" ; else cout << "No" ; } // Driver Code int main() { int arr[] = { 1, 4, 5, 2, 3, 4 }; int n = 6; // Function call solve(arr, n); return 0; } // This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to check if two subsequences exist public static void solve( int [] arr1) { // Temporary array, which will contain // same element and in sorted order // of input array int [] temp = new int [arr1.length]; for ( int i = 0 ; i < arr1.length; i++) { temp[i] = arr1[i]; } Arrays.sort(temp); // Counter to iterate on temp[] array // to find elements in sorted manner. int counter = 0 ; // New array which will store searched elements // in two iterations. int [] arr = new int [arr1.length]; // Loop for searching twice in input array. for ( int i = 0 ; i < 2 ; i++) { // Loop to search for elements in // sorted manner in input array. for ( int j = 0 ; j < arr1.length; j++) { // When element at temp[counter] // and arr1[j] matches. if (arr1[j] == temp[counter]) { // Storing that element in array arr[counter] = arr1[j]; counter++; if (counter == temp.length) { break ; } } } } System.out.println(Arrays.equals(arr, temp) == true ? "Yes" : "No" ); } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 4 , 5 , 2 , 3 , 4 }; // Function call solve(arr); } } |
Python3
# Python3 code to implement the approach # Function to check if two subsequences exist def solve(arr1, n) : # Temporary array, which will contain # same element and in sorted order # of input array temp = [ 0 ] * n; for i in range (n) : temp[i] = arr1[i]; temp.sort(); # Counter to iterate on temp[] array # to find elements in sorted manner. counter = 0 ; # New array which will store searched elements # in two iterations. arr = [ 0 ] * n; # Loop for searching twice in input array. for i in range ( 2 ) : # Loop to search for elements in # sorted manner in input array. for j in range (n) : # When element at temp[counter] # and arr1[j] matches. if (arr1[j] = = temp[counter]) : # Storing that element in array arr[counter] = arr1[j]; counter + = 1 ; if (counter = = n) : break ; flag = True ; for i in range (n) : if (arr[i] ! = temp[i]) : flag = False ; break ; if (flag = = True ) : print ( "Yes" ); else : print ( "No" ); # Driver Code if __name__ = = "__main__" : arr = [ 1 , 4 , 5 , 2 , 3 , 4 ]; n = 6 ; # Function call solve(arr, n); # This code is contributed by Rohit Pradhan |
C#
// C# code to implement the approach using System; class GFG { // Function to check if two subsequences exist public static void solve( int [] arr1) { // Temporary array, which will contain // same element and in sorted order // of input array int [] temp = new int [arr1.Length]; for ( int i = 0; i < arr1.Length; i++) { temp[i] = arr1[i]; } Array.Sort(temp); // Counter to iterate on temp[] array // to find elements in sorted manner. int counter = 0; // New array which will store searched elements // in two iterations. int [] arr = new int [arr1.Length]; // Loop for searching twice in input array. for ( int i = 0; i < 2; i++) { // Loop to search for elements in // sorted manner in input array. for ( int j = 0; j < arr1.Length; j++) { // When element at temp[counter] // and arr1[j] matches. if (arr1[j] == temp[counter]) { // Storing that element in array arr[counter] = arr1[j]; counter++; if (counter == temp.Length) { break ; } } } } bool isEqual = Array.Equals(arr, temp); Console.Write(!isEqual == true ? "Yes" : "No" ); } // Driver Code static public void Main (){ int [] arr = { 1, 4, 5, 2, 3, 4 }; // Function call solve(arr); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // Javascript code to implement the approach // Function to check if two subsequences exist function solve(arr1,n) { // Temporary array, which will contain // same element and in sorted order // of input array let temp= new Array(n); for (let i = 0; i < n; i++) { temp[i] = arr1[i]; } temp.sort( function (a, b) { return a - b; }); // Counter to iterate on temp[] array // to find elements in sorted manner. let counter = 0; // New array which will store searched elements // in two iterations. let arr= new Array(n); // Loop for searching twice in input array. for (let i = 0; i < 2; i++) { // Loop to search for elements in // sorted manner in input array. for (let j = 0; j < n; j++) { // When element at temp[counter] // and arr1[j] matches. if (arr1[j] == temp[counter]) { // Storing that element in array arr[counter] = arr1[j]; counter++; if (counter == n) { break ; } } } } let flag = true ; for (let i = 0; i < n; i++) { if (arr[i] != temp[i]) { flag = false ; break ; } } if (flag == true ) document.write( "Yes" ); else document.write( "No" ); } // Driver Code let arr = [ 1, 4, 5, 2, 3, 4 ]; let n = 6; // Function call solve(arr, n); // This code is contributed by satwik4409. </script> |
Yes
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)