tag:blogger.com,1999:blog-6314876008291942531.post8088136167619116290..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Subarray sortedUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-64106120891625049942010-12-16T10:07:24.038-08:002010-12-16T10:07:24.038-08:00Trivial solution: create a clone of the array, sor...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).<br /><br />Optimal solution (sketch): <br />- find first (s) and last (e) index i s.t. arr[i] < arr[i+1]<br />- find vs = min(arr[i]) with s<=i vs<br />- set e to be the last index i s.t. arr[i] < ve<br /><br />it should work (except for some special cases, empty array, etc.)<br />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.<br /><br />Maurizio (from Cagliari)Jack SVitatohttps://www.blogger.com/profile/00769038995512160956noreply@blogger.com