Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Monday, December 6, 2010
Subarray sorted
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.
Trivial solution: create a clone of the array, sort it, and then find first and last difference in the sorted and unsorted arrays. It takes O(n log n).
Optimal solution (sketch): - find first (s) and last (e) index i s.t. arr[i] < arr[i+1] - find vs = min(arr[i]) with s<=i vs - set e to be the last index i s.t. arr[i] < ve
it should work (except for some special cases, empty array, etc.) Infact, all elements before s are sorted, as well as the ones after e; elements before s are <= than those after s; elements after e are >= than those before e.
Trivial solution: create a clone of the array, sort it, and then find first and last difference in the sorted and unsorted arrays. It takes O(n log n).
ReplyDeleteOptimal solution (sketch):
- find first (s) and last (e) index i s.t. arr[i] < arr[i+1]
- find vs = min(arr[i]) with s<=i vs
- set e to be the last index i s.t. arr[i] < ve
it should work (except for some special cases, empty array, etc.)
Infact, all elements before s are sorted, as well as the ones after e; elements before s are <= than those after s; elements after e are >= than those before e.
Maurizio (from Cagliari)