Friday, January 27, 2012

Minimum length unsorted subarray to make a sorted array

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.

http://www.geeksforgeeks.org/minimum-length-unsorted-subarray-sorting-which-makes-the-complete-array-sorted/
https://noobtogeek.wordpress.com/2014/03/25/find-the-minimum-length-unsorted-subarray-sorting-which-makes-the-complete-array-sorted/

Method :
a) Scan from left to right and find the first element which is greater than the next element. Let s be the index of such an element.
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order). Let e be the index of such an element.
c) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max.
d) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.
e) Find the last element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.

No comments:

Post a Comment