Min subarray (or sublist) to sort to make an unsorted array (or list) sorted - Algorithms and Problem SolvingAlgorithms and Problem Solving
Give a list of unsorted number, find the min window or min sublist or min subarray of the input, such as if sublist is sorted, the whole list is sorted too.
For example, given array a={1,2,3,5,4,4,3,3,7,8,9} then min subarray to sort the complete array sorted is {5,4,3,3}. More example : for a={1,2,3,5,6,4,2,3,3,7,8,9} then min subarray is {2,3,5,6,4,2,3,3}, for a={1,2,3,5,6,4,3,3,7,8,9,2} then min subarray is {2,3,5,6,4,2,3,3,7,8,9,2} etc.
Apparently the problems looks very complicated. But if we look into an example then we will see that it is rather one of simpler problems. Just believe in your intuition!
For example, a={1,2,3,5,4,4,3,3,7,8,9}. Note that 4 comes after 5 breaking the ascending sorting order. We understand the 5 and 4 must be contained in the resultant min subarray. Now believe in your intuition. How did you figure out that 5,4,3,3 is the answer? Because our brain affixed our attention to the two numbers : 5 and the right most 3. this is because these two numbers are related. How? Because 5 tells us the first number to be included in the min list. This also tells us that the left of 5 , i.e. 3 is the minimum number that may appear in the min list(why?).
We identified the start of the min list. But where does it end? As we know that 3 may be the minimum that ma appear in the list. This means the min list should contain all number greater than equal to 3 starting from 5. So, if we can identify somehow the max number that may appear in this min list then the minList ends at the position which has a higher value than the max number (why?).
What is the maximum number that can appear in the list? As we know 3 is the min then we can identify the right most 3 and get the maximum among elements between the left boundary i.e. 5 and rightmost min i.e. rightmost 3. The maximum tells us where is the rightmost boundary of the min array. The right boundary is the first number greater than the max on the right of the right most min. For example, in the current example it is 7. Then all numbers from 5 until 7 (excluding 7) constitute the resulting min subarray.
Below is the implementation of the above idea. The algorithm runs in O(n) time and O(1) space.
Read full article from Min subarray (or sublist) to sort to make an unsorted array (or list) sorted - Algorithms and Problem SolvingAlgorithms and Problem Solving
