Split given Array in minimum number of subarrays such that rearranging the order of subarrays sorts the array
Given an array arr[] consisting of N integers, the task is to find the minimum number of splitting of array elements into subarrays such that rearranging the order of subarrays sorts the given array.
Examples:
Input: arr[] = {6, 3, 4, 2, 1}
Output: 4
Explanation:
The given array can be divided into 4 subarrays as {6}, {3, 4}, {2}, {1} and these subarrays can be rearranged as {1}, {2}, {3, 4}, {6}. The resulting array will be {1, 2, 3, 4, 6} which is sorted. So, the minimum subarrays the given array can be divided to sort the array is 4.Input: arr[] = {1, -4, 0, -2}
Output: 4
Approach: The given problem can be solved by maintaining a sorted version of the array arr[] and grouping together all integers in the original array which appear in the same sequence as in the sorted array. Below are the steps:
- Maintain a vector of pair V that stores the value of the current element and the index of the current element of the array arr[] for all elements in the given array.
- Sort the vector V.
- Initialize a variable, say cnt as 1 that stores the minimum number of subarrays required.
- Traverse the vector V for i in the range [1, N – 1] and perform the following steps:
- If the index of the ith element in the original array is (1 + index of (i – 1)th element) in the original array, then the two can be grouped together in the same subarray.
- Otherwise, the two elements need to be in separate subarrays and increment the value of cnt by 1.
- After completing the above steps, print the value of cnt as the resultant possible breaking of subarrays.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find minimum number of // subarrays such that rearranging the // subarrays sort the array int numberOfSubarrays( int arr[], int n) { // Stores the minimum number of // subarrays int cnt = 1; // Stores all the elements in the // array with their indices vector<pair< int , int > > v(n); // Copy array elements in vector for ( int i = 0; i < n; i++) { v[i].first = arr[i]; v[i].second = i; } // Sort the vector v sort(v.begin(), v.end()); // Iterate through vector v for ( int i = 1; i < n; i++) { // If the (i)th and (i-1)th element // can be grouped in same subarray if (v[i].second == v[i - 1].second + 1) { continue ; } else { cnt++; } } // Return resultant count return cnt; } // Driver Code int main() { int arr[] = { 6, 3, 4, 2, 1 }; int N = sizeof (arr) / sizeof (arr[0]); cout << numberOfSubarrays(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to find minimum number of // subarrays such that rearranging the // subarrays sort the array static int numberOfSubarrays( int arr[], int n) { // Stores the minimum number of // subarrays int cnt = 1 ; // Stores all the elements in the // array with their indices pair[] v = new pair[n]; // Copy array elements in vector for ( int i = 0 ; i < n; i++) { v[i] = new pair( 0 , 0 ); v[i].first = arr[i]; v[i].second = i; } // Sort the vector v Arrays.sort(v,(a,b)->a.first-b.first); // Iterate through vector v for ( int i = 1 ; i < n; i++) { // If the (i)th and (i-1)th element // can be grouped in same subarray if (v[i].second == v[i - 1 ].second + 1 ) { continue ; } else { cnt++; } } // Return resultant count return cnt; } // Driver Code public static void main(String[] args) { int arr[] = { 6 , 3 , 4 , 2 , 1 }; int N = arr.length; System.out.print(numberOfSubarrays(arr, N)); } } // This code is contributed by 29AjayKumar |
Python3
# Python Program to implement # the above approach # Function to find minimum number of # subarrays such that rearranging the # subarrays sort the array def numberOfSubarrays(arr, n): # Stores the minimum number of # subarrays cnt = 1 # Stores all the elements in the # array with their indices v = [] # Copy array elements in vector for i in range (n): v.append({ 'first' : arr[i], 'second' : i}) # Sort the vector v v = sorted (v, key = lambda i: i[ 'first' ]) # Iterate through vector v for i in range ( 1 , n): # If the (i)th and (i-1)th element # can be grouped in same subarray if (v[i][ 'second' ] = = v[i - 1 ][ 'second' ] + 1 ): continue else : cnt + = 1 # Return resultant count return cnt # Driver Code arr = [ 6 , 3 , 4 , 2 , 1 ] N = len (arr) print (numberOfSubarrays(arr, N)) # This code is contributed by gfgking |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ class pair : IComparable<pair> { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } public int CompareTo(pair other) { // return other.Salary.CompareTo(this.Salary); if ( this .first < other.first) { return 1; } else if ( this .first > other.first) { return -1; } else { return 0; } } } // Function to find minimum number of // subarrays such that rearranging the // subarrays sort the array static int numberOfSubarrays( int []arr, int n) { // Stores the minimum number of // subarrays int cnt = 1; // Stores all the elements in the // array with their indices pair[] v = new pair[n]; // Copy array elements in vector for ( int i = 0; i < n; i++) { v[i] = new pair(0,0); v[i].first = arr[i]; v[i].second = i; } // Sort the vector v Array.Sort(v); // Iterate through vector v for ( int i = 1; i < n; i++) { // If the (i)th and (i-1)th element // can be grouped in same subarray if (v[i].second == v[i - 1].second + 1) { continue ; } else { cnt++; } } // Return resultant count return cnt; } // Driver Code public static void Main(String[] args) { int []arr = { 6, 3, 4, 2, 1 }; int N = arr.Length; Console.Write(numberOfSubarrays(arr, N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find minimum number of // subarrays such that rearranging the // subarrays sort the array function numberOfSubarrays(arr, n) { // Stores the minimum number of // subarrays let cnt = 1; // Stores all the elements in the // array with their indices let v = []; // Copy array elements in vector for (let i = 0; i < n; i++) { v.push({ first: arr[i], second: i }) } // Sort the vector v v.sort( function (a, b) { return a.first - b.first }) // Iterate through vector v for (let i = 1; i < n; i++) { // If the (i)th and (i-1)th element // can be grouped in same subarray if (v[i].second == v[i - 1].second + 1) { continue ; } else { cnt++; } } // Return resultant count return cnt; } // Driver Code let arr = [6, 3, 4, 2, 1]; let N = arr.length; document.write(numberOfSubarrays(arr, N)); // This code is contributed by Potta Lokesh </script> |
4
Time Complexity: O(N*log N)
Auxiliary Space: O(N)