{"id":1038,"date":"2020-06-11T10:25:06","date_gmt":"2020-06-11T10:25:06","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1038"},"modified":"2022-03-30T22:03:32","modified_gmt":"2022-03-30T22:03:32","slug":"sort-in-a-unique-way","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/sort-in-a-unique-way\/","title":{"rendered":"Sort in a unique way"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For a given array find the length of largest sorted sub-array in it, but if the current array is not sorted, we divide the array into two halves and then check them for sorting.<\/p>\n<\/blockquote>\n

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

Test Case:<\/h4>\n
Input:\n1\n8\n11 12 1 2 13 14 3 4\n\nOutput:\n2\n\nExplanation:\nSorted sub arrays are [11,12], [1,2], [13,14] and [3,4]. Maximum size is 2. So our answer is 2.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) We can divide array recursively, and check if the current subarray is sorted or not,. If yes, we return the length of the sub-array. Parent array returns the maximum of the values returned from its sub-arrays or its length if the parent array is sorted.<\/p>\n
2)  Dividing array takes O(log(N))<\/code> time, for each array we get, we check if it is sorted or not, where it takes another O(N)<\/code> time. So, whole approach take O(N<\/code>2<\/sup> x Log(N) )<\/code> time. This approach takes a longer time to process an array with a larger number of elements, so we move to a better and efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/h4>\n
\n
1) We can use recursion to solve this problem, by dividing the current array into two halves recursively and return 1 when the array size is 1 as an array of size 1 is already sorted.<\/p>\n
2) Every subarray returns the length of the largest sorted sub-array of it.<\/p>\n
3) If we receive the same lengths from both sub-arrays, we check if the last element of the left sub-array is less than the starting element of the right sub-array.<\/p>\n
4) From the above conditions, we can observe that both sub-arrays are sorted and also the whole parent array is sorted, so we return the length of the parent array.<\/p>\n
5) If not, we compare length received from both sub-arrays and return the maximum of both lengths received.<\/p>\n<\/blockquote>\n
EXAMPLE:<\/h4>\n
\n
    \n
  • \n
    Let array A<\/code> be [11, 12 ,1 ,2 ,13 ,14 , 3, 4]<\/code>,<\/p>\n<\/li>\n
  • \n
    Recursion tree according to Efficient Approach for the above array would be,<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
    \"\"<\/p>\n
    \n
      \n
    • \n
      When the array is reduced to size 1, it returns 1, as it is already sorted, as we can see in all leaf nodes in above figure.<\/p>\n<\/li>\n
    • \n
      When two nodes return values, parent node returns the maximum of values returned from its child nodes, if both values are the same as the length of child nodes, we check if the last element of the left child is smaller than the first element of the right child. If yes, we return the sum of both child nodes.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
      Solutions:<\/h3>\n\t\t\t\t\t\t