Split given Array in minimum number of subarrays such that rearranging the order of subarrays sorts the array

0 0 5 minutes read

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 i^th 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>

Output

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 zambiatek!