Min unsorted

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