# Rectangular Sweet Box

Post Min array

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A` with `N` elements, your task is to divide the array in `maximum` possible segments such that when these elements are sorted in their individual segments and then all segments are concatenated together, the resultant array should be sorted.

See original problem statement here

Note: Two or more elements can be same.

#### For Example:

``````Input : arr = [3 2 4 5 5]

Output : 4

Explanation : As 4 divisions can be made in the array -> [3 2], , , .
If we sort them individually and concatenate in the same order we get [2 3 4 5 5] which is in sorted order.``````

#### OBSERVATION :

1. For each division to be valid in the array, the `maximum` value at the left division should be less than or equal to the `minimum` value at the right division. If this condition holds true, we can have such valid divisions.
For Example- Suppose we have `[4 7 6 9 8]`, and we wish to have a partition between `7` and `6`. It is not a valid division as `max` value in the left division i.e. `7` is greater than `min` value in the right division i.e. `6` so after division and concatenation, these divisions will not be sorted properly.

2. So in order to determine whether a division is possible at a particular index say `i`. For each index `i`, we should know the `Maximum` value in the left sub-array and the `Minimum` value in the right sub-array.

#### SOLVING APPROACH:

1. idea is to go through some online coding classes and use `Post Min Array`. This array is used to store the `Minimum` value present at the right of an original array from a particular index.
For Example-
`A` = `[5 1 3 2 7 8 6]`
`PostMin` = `[1 1 2 2 6 6 6]`

2. We will construct a `Post Min Array` for our array so that for every index `i`, we know the `Minimum` value that is present at the right of it.

3. For keeping track of `Maximum` value at every index, we will initialize a `Max` value and while traversing the array we will update it for every element.

4. Now we will start traversing the array and checking whether the `Maximum` value at left sub-array is less than or equal to the `Minimum` value at right sub-array. If `Yes` increment `count` by `1`.

#### SOLUTIONS:

```#include <stdio.h>
#include <limits.h>

int min(int a, int b){
return (a<b)? a:b;
}

int max(int a, int b){
return (a>b)? a:b;
}

int maxDivide(int *arr, int n){

/* creating postmin array */
int lmin[n+1];
lmin[n] = INT_MAX;

for(int i=n-1; i>=0; i--){
lmin[i] = min(arr[i], lmin[i+1]);
}

int count = 0;
int v = INT_MIN;

for(int i=0; i<n; i++){
v = max(v, arr[i]);
if(v <= lmin[i+1])
count++;
}
return count;
}
int main()
{
int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
int arr[n];

for(int i=0; i<n; i++)
scanf("%d", &arr[i]);

printf("%d\n", maxDivide(arr, n));
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

int maxDivide(int *arr, int n){

/* creating postmin array */
int lmin[n+1] = {0};
lmin[n] = INT_MAX;

for(int i=n-1; i>=0; i--){
lmin[i] = min(arr[i], lmin[i+1]);
}

int count = 0;
int v = INT_MIN;

for(int i=0; i<n; i++){
v = max(v, arr[i]);
if(v <= lmin[i+1])
count++;
}
return count;
}
int main()
{
int t; cin>>t;
while(t--){
int n; cin>>n;
int arr[n];

for(int i=0; i<n; i++)
cin>>arr[i];

cout<<maxDivide(arr, n)<<"\n";
}
return 0;
}

```
```
import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
static int maxDivide(int []arr, int n){

/* creating postmin array */
int lmin[] = new int[n+1];
lmin[n] = Integer.MAX_VALUE;

for(int i=n-1; i>=0; i--){
lmin[i] = Math.min(arr[i], lmin[i+1]);
}

int count = 0;
int v = Integer.MIN_VALUE;

for(int i=0; i<n; i++){
v = Math.max(v, arr[i]);
if(v <= lmin[i+1])
count++;
}
return count;
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int arr[] = new int[n];

for(int i=0; i<n; i++)
arr[i] = sc.nextInt();

System.out.println(maxDivide(arr, n));
t--;
}
}
}

```

#### Refer video for Quick Explanation: 