Maximize partitions that if sorted individually makes the whole Array sorted

Given an array arr[]. The task is to divide arr[] into the maximum number of partitions, such that, those partitions if sorted individually make the whole array sorted.

Examples:

Input: arr[] = { 28, 9, 18, 32, 60, 50, 75, 70 }
Output: 4
Explanation: Following are the partitions in which the array is divided. 
If we divide arr[] into four partitions {28, 9, 18}, {32}, { 60, 50}, and {75, 70}, sort them and concatenate. 
Sorting all of them indivudually makes the whole array sorted. 
Hence, 4 is the answer.

Input: arr[] = { 2, 1, 0, 3, 4, 5 }
Output: 4

Approach: This problem is implementation-based. Follow the steps below to solve the given problem.  

• Create a maximum array that calculates the maximum element to the left till that index of the array.
• Create a minimum array that calculates the minimum element to the right till that index of the array.
• Iterate through the array, each time all elements to the leftMax[] are smaller (or equal) to all elements to the rightMin[], that means there is a new chunk, so increment the count by 1.
• Return count+1 as the final answer.

Below is the implementation of the above approach. 

// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find maximum partitions. int maxPartitions(vector<int>& arr) {  int N = arr.size();  // To keep track of max  // and min elements at every index  vector<int> leftMax(arr.size());  vector<int> rightMin(arr.size());  leftMax[0] = arr[0];  for (int i = 1; i < N; i++) {  leftMax[i] = max(leftMax[i - 1],  arr[i]);  }  rightMin[N - 1] = arr[N - 1];  for (int i = N - 2; i >= 0; i--) {  rightMin[i] = min(rightMin[i + 1],  arr[i]);  }  int count = 0;  for (int i = 0; i < N - 1; i++) {  if (leftMax[i] <= rightMin[i + 1]) {  count++;  }  }  // Return count + 1 as the final answer  return count + 1; } // Driver code int main() {  vector<int> arr{ 10, 0, 21, 32, 68 };  cout << maxPartitions(arr);  return 0; } 

// Java implementation of the above approach import java.util.*; public class GFG {  // Function to find maximum partitions.  static int maxPartitions(int[] arr)  {  int N = arr.length;  // To keep track of max  // and min elements at every index  int[] leftMax = new int[arr.length];  int[] rightMin = new int[arr.length];  leftMax[0] = arr[0];  for (int i = 1; i < N; i++) {  leftMax[i] = Math.max(leftMax[i - 1], arr[i]);  }  rightMin[N - 1] = arr[N - 1];  for (int i = N - 2; i >= 0; i--) {  rightMin[i] = Math.min(rightMin[i + 1], arr[i]);  }  int count = 0;  for (int i = 0; i < N - 1; i++) {  if (leftMax[i] <= rightMin[i + 1]) {  count++;  }  }  // Return count + 1 as the final answer  return count + 1;  }  // Driver code  public static void main(String args[])  {  int[] arr = { 10, 0, 21, 32, 68 };  System.out.println(maxPartitions(arr));  } } // This code is contributed by Samim Hossain Mondal. 

# Python program for above approach # Function to find maximum partitions. def maxPartitions(arr): N = len(arr) # To keep track of max # and min elements at every index leftMax = [] rightMin = [] leftMax.append(arr[0]) for i in range(1, N): leftMax.append(max(leftMax[i - 1], arr[i])) rightMin.append(arr[N - 1]) for i in range(1, N): rightMin.append(min(rightMin[i - 1], arr[N - i - 1])) rightMin.reverse() count = 0 for i in range(0, N - 1): if (leftMax[i] <= rightMin[i + 1]): count = count + 1 # Return count + 1 as the final answer return count + 1 # Driver code arr = [10, 0, 21, 32, 68] print(maxPartitions(arr)) # This code is contributed by Samim Hossain Mondal. 

// C# program for above approach using System; class GFG {  // Function to find maximum partitions.  static int maxPartitions(int[] arr)  {  int N = arr.Length;  // To keep track of max  // and min elements at every index  int[] leftMax = new int[arr.Length];  int[] rightMin = new int[arr.Length];  leftMax[0] = arr[0];  for (int i = 1; i < N; i++) {  leftMax[i] = Math.Max(leftMax[i - 1], arr[i]);  }  rightMin[N - 1] = arr[N - 1];  for (int i = N - 2; i >= 0; i--) {  rightMin[i] = Math.Min(rightMin[i + 1], arr[i]);  }  int count = 0;  for (int i = 0; i < N - 1; i++) {  if (leftMax[i] <= rightMin[i + 1]) {  count++;  }  }  // Return count + 1 as the final answer  return count + 1;  }  // Driver code  public static void Main()  {  int[] arr = { 10, 0, 21, 32, 68 };  Console.WriteLine(maxPartitions(arr));  } } // This code is contributed by ukasp. 

 <script>  // JavaScript code for the above approach   // Function to find maximum partitions.  function maxPartitions(arr)  {  let N = arr.length;  // To keep track of max  // and min elements at every index  let leftMax = new Array(arr.length);  let rightMin = new Array(arr.length);  leftMax[0] = arr[0];  for (let i = 1; i < N; i++) {  leftMax[i] = Math.max(leftMax[i - 1],  arr[i]);  }  rightMin[N - 1] = arr[N - 1];  for (let i = N - 2; i >= 0; i--) {  rightMin[i] = Math.min(rightMin[i + 1],  arr[i]);  }  let count = 0;  for (let i = 0; i < N - 1; i++) {  if (leftMax[i] <= rightMin[i + 1]) {  count++;  }  }  // Return count + 1 as the final answer  return count + 1;  }  // Driver code  let arr = [10, 0, 21, 32, 68];  document.write(maxPartitions(arr));  // This code is contributed by Potta Lokesh  </script> 

4

Time Complexity: O(N)
Auxiliary Space: O(N)