Algorithms‎ > ‎Array‎ > ‎

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



Comments