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 arrayint 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 Codeint 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 approachimport 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 arraystatic 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 Codepublic 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 arraydef 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 Codearr = [6, 3, 4, 2, 1]N = len(arr)print(numberOfSubarrays(arr, N))Â
# This code is contributed by gfgking |
C#
// C# program for the above approachusing 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 arraystatic 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 Codepublic 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> |
Output
4
Time Complexity: O(N*log N)
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!
