{"id":25232,"date":"2017-10-15T15:57:17","date_gmt":"2017-10-15T10:27:17","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25232"},"modified":"2017-10-15T15:57:17","modified_gmt":"2017-10-15T10:27:17","slug":"find-minimum-length-unsorted-subarray-sorting-makes-complete-array-sorted","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-minimum-length-unsorted-subarray-sorting-makes-complete-array-sorted\/","title":{"rendered":"Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted"},"content":{"rendered":"<p>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.<span id=\"more-8858\"><\/span><br \/>\n<strong><br \/>\nExamples:<\/strong><br \/>\n1) 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.<\/p>\n<p>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.<br \/>\n<a href=\"http:\/\/www.practice.geeksforgeeks.org\/problem-page.php?pid=573\" target=\"_blank\" rel=\"noopener noreferrer\"><br \/>\n<\/a><\/p>\n<p>We strongly recommend that you click here and practice it, before moving on to the solution.<br \/>\n<strong>Solution:<\/strong><br \/>\n<strong>1) Find the candidate unsorted subarray <\/strong><br \/>\na) Scan from left to right and find the first element which is greater than the next element. Let <em>s <\/em>be the index of such an element. In the above example 1, <em>s <\/em>is 3 (index of 30).<br \/>\nb) 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 <em>e <\/em>be the index of such an element. In the above example 1, e is 7 (index of 31).<\/p>\n<p><strong>2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.<\/strong><br \/>\na) Find the minimum and maximum values in <em>arr[s..e]<\/em>. Let minimum and maximum values be <em>min <\/em>and <em>max<\/em>. <em>min <\/em>and <em>max <\/em>for [30, 25, 40, 32, 31] are 25 and 40 respectively.<br \/>\nb) Find the first element (if there is any) in <em>arr[0..s-1]<\/em> which is greater than <em>min<\/em>, change <em>s <\/em>to index of this element. There is no such element in above example 1.<br \/>\nc) Find the last element (if there is any) in <em>arr[e+1..n-1] <\/em>which is smaller than max, change <em>e <\/em>to index of this element. In the above example 1, e is changed to 8 (index of 35)<\/p>\n<p><strong>3) Print <em>s <\/em>and <em>e<\/em>.<\/strong><\/p>\n<p>\u00a0<\/p>\n<p><strong>Implementation:<\/strong><\/p>\n<p><strong>c<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%20%0Avoid%20printUnsorted(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20int%20s%20%3D%200%2C%20e%20%3D%20n-1%2C%20i%2C%20max%2C%20min%3B%20%20%20%0A%20%20%0A%20%20%2F%2F%20step%201(a)%20of%20above%20algo%0A%20%20for%20(s%20%3D%200%3B%20s%20%3C%20n-1%3B%20s%2B%2B)%0A%20%20%7B%0A%20%20%20%20if%20(arr%5Bs%5D%20%3E%20arr%5Bs%2B1%5D)%0A%20%20%20%20%20%20break%3B%0A%20%20%7D%0A%20%20if%20(s%20%3D%3D%20n-1)%0A%20%20%7B%0A%20%20%20%20printf(%22The%20complete%20array%20is%20sorted%22)%3B%0A%20%20%20%20return%3B%0A%20%20%7D%0A%20%20%0A%20%20%2F%2F%20step%201(b)%20of%20above%20algo%0A%20%20for(e%20%3D%20n%20-%201%3B%20e%20%3E%200%3B%20e\u2013)%0A%20%20%7B%0A%20%20%20%20if(arr%5Be%5D%20%3C%20arr%5Be-1%5D)%0A%20%20%20%20%20%20break%3B%0A%20%20%7D%0A%20%20%0A%20%20%2F%2F%20step%202(a)%20of%20above%20algo%0A%20%20max%20%3D%20arr%5Bs%5D%3B%20min%20%3D%20arr%5Bs%5D%3B%0A%20%20for(i%20%3D%20s%20%2B%201%3B%20i%20%3C%3D%20e%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20if(arr%5Bi%5D%20%3E%20max)%0A%20%20%20%20%20%20max%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20if(arr%5Bi%5D%20%3C%20min)%0A%20%20%20%20%20%20min%20%3D%20arr%5Bi%5D%3B%0A%20%20%7D%0A%20%20%0A%20%20%2F%2F%20step%202(b)%20of%20above%20algo%0A%20%20for(%20i%20%3D%200%3B%20i%20%3C%20s%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20if(arr%5Bi%5D%20%3E%20min)%0A%20%20%20%20%7B%20%20%0A%20%20%20%20%20%20s%20%3D%20i%3B%0A%20%20%20%20%20%20break%3B%0A%20%20%20%20%7D%20%20%20%20%20%20%0A%20%20%7D%20%0A%20%20%0A%20%20%2F%2F%20step%202(c)%20of%20above%20algo%0A%20%20for(%20i%20%3D%20n%20-1%3B%20i%20%3E%3D%20e%2B1%3B%20i\u2013)%0A%20%20%7B%0A%20%20%20%20if(arr%5Bi%5D%20%3C%20max)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20e%20%3D%20i%3B%0A%20%20%20%20%20%20break%3B%0A%20%20%20%20%7D%20%0A%20%20%7D%20%20%0A%20%20%20%20%20%20%0A%20%20%2F%2F%20step%203%20of%20above%20algo%0A%20%20printf(%22%20The%20unsorted%20subarray%20which%20makes%20the%20given%20array%20%22%0A%20%20%20%20%20%20%20%20%20%22%20sorted%20lies%20between%20the%20indees%20%25d%20and%20%25d%22%2C%20s%2C%20e)%3B%0A%20%20return%3B%0A%7D%0A%20%20%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B10%2C%2012%2C%2020%2C%2030%2C%2025%2C%2040%2C%2032%2C%2031%2C%2035%2C%2050%2C%2060%7D%3B%0A%20%20int%20arr_size%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20printUnsorted(arr%2C%20arr_size)%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>JAVA<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20Main%0A%7B%0A%20%20%20%20static%20void%20printUnsorted(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20int%20s%20%3D%200%2C%20e%20%3D%20n-1%2C%20i%2C%20max%2C%20min%3B%20%20%20%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F%2F%20step%201(a)%20of%20above%20algo%0A%20%20%20%20%20%20for%20(s%20%3D%200%3B%20s%20%3C%20n-1%3B%20s%2B%2B)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(arr%5Bs%5D%20%3E%20arr%5Bs%2B1%5D)%0A%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20if%20(s%20%3D%3D%20n-1)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20System.out.println(%22The%20complete%20array%20is%20sorted%22)%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F%2F%20step%201(b)%20of%20above%20algo%0A%20%20%20%20%20%20for(e%20%3D%20n%20-%201%3B%20e%20%3E%200%3B%20e\u2013)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(arr%5Be%5D%20%3C%20arr%5Be-1%5D)%0A%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F%2F%20step%202(a)%20of%20above%20algo%0A%20%20%20%20%20%20max%20%3D%20arr%5Bs%5D%3B%20min%20%3D%20arr%5Bs%5D%3B%0A%20%20%20%20%20%20for(i%20%3D%20s%20%2B%201%3B%20i%20%3C%3D%20e%3B%20i%2B%2B)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(arr%5Bi%5D%20%3E%20max)%0A%20%20%20%20%20%20%20%20%20%20max%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20if(arr%5Bi%5D%20%3C%20min)%0A%20%20%20%20%20%20%20%20%20%20min%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F%2F%20step%202(b)%20of%20above%20algo%0A%20%20%20%20%20%20for(%20i%20%3D%200%3B%20i%20%3C%20s%3B%20i%2B%2B)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(arr%5Bi%5D%20%3E%20min)%0A%20%20%20%20%20%20%20%20%7B%20%20%0A%20%20%20%20%20%20%20%20%20%20s%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%7D%20%20%20%20%20%20%0A%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F%2F%20step%202(c)%20of%20above%20algo%0A%20%20%20%20%20%20for(%20i%20%3D%20n%20-1%3B%20i%20%3E%3D%20e%2B1%3B%20i\u2013)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(arr%5Bi%5D%20%3C%20max)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20e%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%7D%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%2F%2F%20step%203%20of%20above%20algo%0A%20%20%20%20%20%20System.out.println(%22%20The%20unsorted%20subarray%20which%22%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%20makes%20the%20given%20array%20sorted%20lies%22%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%20%20between%20the%20indices%20%22%2Bs%2B%22%20and%20%22%2Be)%3B%0A%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%20%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B10%2C%2012%2C%2020%2C%2030%2C%2025%2C%2040%2C%2032%2C%2031%2C%2035%2C%2050%2C%2060%7D%3B%0A%20%20%20%20%20%20int%20arr_size%20%3D%20arr.length%3B%0A%20%20%20%20%20%20printUnsorted(arr%2C%20arr_size)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201djava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Time Complexity: <\/strong>O(n)<\/p>\n<p>Please write comments if you find the above code\/algorithm incorrect, or find better ways to solve the same problem.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted -Searching and sorting &#8211; Given an unsorted array arr[] of size n. find the minimum length subarray arr[s..e]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670,83510],"tags":[71128,71222,70962,71133,71893,2380,71127,70461,71121,72377,71134,71141,70978,71131,70531,70975,72378,71123,71130,71122,71129,71139,70780,72379,72305,71146,72381,70533,71144,72374,70928,70966,71216,70017,70976,72376,71158,70969,72308,70046,71714,71712,71120,70016,70961,70548,70960,72382,72380,72299,71695,70020,72304,71149,70967,71219,71142,72375,72185],"class_list":["post-25232","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","category-unsorted-subarray","tag-algorithm-for-bubble-sort","tag-algorithm-for-insertion-sort","tag-algorithm-for-selection-sort","tag-algorithm-of-bubble-sort","tag-algorithm-sort","tag-array-sort","tag-bubble-short","tag-bubble-sort","tag-bubble-sort-algorithm","tag-bubble-sort-algorithm-c-code","tag-bubble-sort-algorithm-with-example","tag-bubble-sort-animation","tag-bubble-sort-c","tag-bubble-sort-code","tag-bubble-sort-complexity","tag-bubble-sort-example","tag-bubble-sort-example-c","tag-bubble-sort-in-c","tag-bubble-sort-in-data-structure","tag-bubble-sort-java","tag-bubble-sort-program","tag-bubble-sort-pseudocode","tag-bubblesort","tag-c-bubble-sort-example","tag-c-sort","tag-comparison-of-sorting-algorithms","tag-complete-array","tag-complexity-of-bubble-sort","tag-different-sorting-algorithms","tag-find-the-minimum-length-unsorted-subarray","tag-heap-sort-algorithm","tag-insert-sort","tag-insertion-sort","tag-insertion-sort-algorithm","tag-insertion-sort-example","tag-java-bubble-sort","tag-java-sort","tag-java-sorting-algorithms","tag-list-of-sorting-algorithms","tag-quicksort","tag-quicksort-algorithm-in-data-structure","tag-quicksort-algorithm-with-example","tag-selection-sort","tag-selection-sort-algorithm","tag-selection-sort-example","tag-selection-sort-in-data-structure","tag-selection-sort-java","tag-simple-sort-c","tag-sort-an-array","tag-sort-c","tag-sorted","tag-sorting-algorithms","tag-sorting-algorithms-c-code","tag-sorting-algorithms-in-data-structures","tag-sorting-algorithms-java","tag-sorting-in-c","tag-sorting-in-data-structure","tag-sorting-which-makes-the-complete-array-sorted","tag-sortings"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25232","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25232"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25232\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25232"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25232"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}