Given an array arr[] of N distinct integers, the task is to check if it is possible to sort the array in increasing order by performing the following operations in order exactly once:
- Split the array arr[] into exactly Y(1 <= Y <= N) non-empty subarrays such that each element belongs to exactly one subarray.
- Reorder the subarrays in any arbitrary order.
- Merge the reordered subarrays.
Examples:
Input: arr[ ] = {6, 3, 4, 2, 1}, Y = 4
Output: Yes
Explanation:
The operations can be performed as:
- Split the array into exactly 4 non-empty subarrays: {6, 3, 4, 2, 1} -> {6}, {3, 4}, {2}, {1}
- Reorder the subarrays: {6}, {3, 4}, {2}, {1} -> {1}, {2}, {3, 4}, {6}
- Merging the subarrays: {1}, {2}, {3, 4}, {6} -> {1, 2, 3, 4, 6} (sorted)
Input: arr[ ] = {1, -4, 0, -2}, Y = 2
Output: No
Approach: The main idea is if the minimum number of splits required to sort the given array arr[] is less than or equal to Y, then it is always possible to sort the array. Also, the required number of splits must be equal to the count of the minimum number of splits required to divide the array into the minimum number of non-decreasing subarrays.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Initialization of pair pair< int , int > a[100001]; // Function to check if it is possible // to sort the array by performing the // operations exactly once in order void checkForSortedSubarray( int n, int y, int arr[]) { // Traversing the array for ( int i = 1; i <= n; i++) { // Storing the array element // in the first part of pair a[i].first = arr[i]; // Storing the index as second // element in the pair a[i].second = i; } // Initialize Count int cnt = 1; // Sorting the array sort(a + 1, a + n + 1); for ( int i = 1; i <= n - 1; i++) { // Checking if the index lies // in order if (a[i].second != a[i + 1].second - 1) cnt++; } // If minimum splits required is // greater than y if (cnt > y) cout << "No" ; else cout << "Yes" ; } // Driver Code int main() { int Y = 4; int arr[] = { 6, 3, 4, 2, 1 }; int N = sizeof (arr) / sizeof (arr[0]); checkForSortedSubarray(N, Y, arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Initialization of pair static pair []a = new pair[ 100001 ]; static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to check if it is possible // to sort the array by performing the // operations exactly once in order static void checkForSortedSubarray( int n, int y, int arr[]) { // Traversing the array for ( int i = 1 ; i <= n; i++) { // Storing the array element // in the first part of pair a[i].first = arr[i]; // Storing the index as second // element in the pair a[i].second = i; } // Initialize Count int cnt = 1 ; // Sorting the array Arrays.sort(a,(a, b) -> a.first - b.first); for ( int i = 1 ; i <= n - 1 ; i++) { // Checking if the index lies // in order if (a[i].second != a[i + 1 ].second - 1 ) cnt++; } // If minimum splits required is // greater than y if (cnt > y) System.out.print( "No" ); else System.out.print( "Yes" ); } // Driver Code public static void main(String[] args) { int Y = 4 ; int arr[] = { 6 , 3 , 4 , 2 , 1 }; int N = arr.length; for ( int i = 0 ;i<a.length;i++) { a[i] = new pair( 0 , 0 ); } checkForSortedSubarray(N- 1 , Y, arr); } } // This code is contributed by Princi Singh |
Python3
# Python 3 program for the above approach # Initialization of pair # Function to check if it is possible # to sort the array by performing the # operations exactly once in order def checkForSortedSubarray(n, y, arr, a): # Traversing the array for i in range ( 0 , n, 1 ): # Storing the array element # in the first part of pair a[i][ 0 ] = arr[i] # Storing the index as second # element in the pair a[i][ 1 ] = i # Initialize Count cnt = 1 # Sorting the array a.sort() for i in range ( 0 ,n, 1 ): # Checking if the index lies # in order if (a[i][ 1 ] ! = a[i + 1 ][ 1 ] - 1 ): cnt + = 1 # If minimum splits required is # greater than y if (cnt > y): print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = '__main__' : Y = 4 a = [[ 0 , 0 ] for i in range ( 100001 )] arr = [ 6 , 3 , 4 , 2 , 1 ] N = len (arr) checkForSortedSubarray(N, Y, arr,a) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Initialization of pair static List<pair> a = new List<pair>(); public class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to check if it is possible // to sort the array by performing the // operations exactly once in order static void checkForSortedSubarray( int n, int y, int []arr) { // Traversing the array for ( int i = 1; i <= n; i++) { // Storing the array element // in the first part of pair a[i].first = arr[i]; // Storing the index as second // element in the pair a[i].second = i; } // Initialize Count int cnt = 1; // Sorting the array a.Sort((c, b) => c.first - b.first); for ( int i = 1; i <= n - 1; i++) { // Checking if the index lies // in order if (a[i].second != a[i + 1].second - 1) cnt++; } // If minimum splits required is // greater than y if (cnt > y) Console.Write( "No" ); else Console.Write( "Yes" ); } // Driver Code public static void Main(String[] args) { int Y = 4; int []arr = { 6, 3, 4, 2, 1 }; int N = arr.Length; for ( int i = 0; i < 100001; i++) { a.Add( new pair(0, 0)); } checkForSortedSubarray(N - 1, Y, arr); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if it is possible // to sort the array by performing the // operations exactly once in order // Initialization of pair var a = []; function checkForSortedSubarray(n, y, arr) { // Traversing the array for (let i = 0; i < n; i++) { // Storing the array element // in the first part of pair // Storing the index as second // element in the pair a.push({ first: arr[i], second: i }) } // Initialize Count let cnt = 1; // Sorting the array a.sort( function (a, b) { return a.first - b.first; }) for (let i = 0; i < n - 1; i++) { // Checking if the index lies // in order if (a[i].second != a[i + 1].second - 1) cnt++; } // If minimum splits required is // greater than y if (cnt > y) document.write( "No" ); else document.write( "Yes" ); } // Driver Code let Y = 4; let arr = [6, 3, 4, 2, 1]; let N = arr.length; checkForSortedSubarray(N, Y, arr); // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(N Log N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!