Min unsorted
Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
December 6, 2010
Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.
Examples:
1) If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], your program should be able to find that the subarray lies between the indexes 3 and 8.
2) If the input array is [0, 1, 15, 25, 6, 7, 30, 40, 50], your program should be able to find that the subarray lies between the indexes 2 and 5.
Solution:
1. Find the start:
Move right to left, say smallest (s) = 60, if an element is greater than smallest, it is start of unsorted array.
s cur start
60 50 -
50 35 -
35 31 -
31 32 32
31 40 40
31 25 40
25 30 30
25 20 30
25 12 30
25 10 30
2. Find the end:
Move left to right, say biggest (b) = 10, if an element is smaller than biggest, it is end of unsorted array.
b cur end
10 12 -
12 20 -
20 30 -
30 25 25
30 40 25
40 32 32
40 31 31
40 35 35
40 50 35
50 60 35