{"id":640,"date":"2020-06-10T11:21:12","date_gmt":"2020-06-10T11:21:12","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=640"},"modified":"2022-03-30T22:44:43","modified_gmt":"2022-03-30T22:44:43","slug":"rectangular-sweet-box","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/rectangular-sweet-box\/","title":{"rendered":"Rectangular Sweet Box"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Post Min array<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array A<\/code> with N<\/code> elements, your task is to divide the array in maximum<\/code> 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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

\n

Note<\/em><\/strong>: Two or more elements can be same.<\/p>\n<\/blockquote>\n

For Example:<\/h3>\n
Input : arr = [3 2 4 5 5]\n\nOutput : 4\n\nExplanation : As 4 divisions can be made in the array -> [3 2], [4], [5], [5].\nIf we sort them individually and concatenate in the same order we get [2 3 4 5 5] which is in sorted order.<\/code><\/pre>\n
OBSERVATION :<\/h3>\n
\n
    \n
  1. \n
    For each division to be valid in the array, the maximum<\/code> value at the left division should be less than or equal to the minimum<\/code> value at the right division. If this condition holds true, we can have such valid divisions.
    \nFor Example<\/em><\/strong>– Suppose we have [4 7 6 9 8]<\/code>, and we wish to have a partition between 7<\/code> and 6<\/code>. It is not a valid division as max<\/code> value in the left division i.e. 7<\/code> is greater than min<\/code> value in the right division i.e. 6<\/code> so after division and concatenation, these divisions will not be sorted properly.   <\/p>\n<\/li>\n
  2. \n
    So in order to determine whether a division is possible at a particular index say i<\/code>. For each index i<\/code>, we should know the Maximum<\/code> value in the left sub-array and the Minimum<\/code> value in the right sub-array. <\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. \n
      The idea is to use Post Min Array<\/code>. This array is used to store the Minimum<\/code> value present at the right of an original array from a particular index.
      \nFor Example<\/em><\/strong>–
      \nA<\/code> = [5 1 3 2 7 8 6]<\/code>
      \nPostMin<\/code> = [1 1 2 2 6 6 6]<\/code>  <\/p>\n<\/li>\n
    2. \n
      We will construct a Post Min Array<\/code> for our array so that for every index i<\/code>, we know the Minimum<\/code> value that is present at the right of it.<\/p>\n<\/li>\n
    3. \n
      For keeping track of Maximum<\/code> value at every index, we will initialize a Max<\/code> value  and while traversing the array we will update it for every element.<\/p>\n<\/li>\n
    4. \n
      Now we will start traversing the array and checking whether the Maximum<\/code> value at left sub-array is less than or equal to the Minimum<\/code> value at right sub-array. If Yes<\/code> increment count<\/code> by 1<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t