{"id":3397,"date":"2017-12-16T12:13:16","date_gmt":"2017-12-16T06:43:16","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=3397"},"modified":"2017-12-16T12:13:16","modified_gmt":"2017-12-16T06:43:16","slug":"kth-smallest-element-in-an-array","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2017\/12\/16\/kth-smallest-element-in-an-array\/","title":{"rendered":"Kth smallest element in an array"},"content":{"rendered":"<p><b>Problem Statement<\/b> &#8211; Given an unsorted array of N elements, find the k<sup>th<\/sup> smallest element. k<sup>th<\/sup> smallest element is the element at index <em>k<\/em> if the array were sorted.<\/p>\n<p><b>Clues<\/b> &#8211;<\/p>\n<ul>\n<li>Solution should be O(N) in time and O(1) in space.<\/li>\n<li>Can you think of a divide-and-conquer based solution?<\/li>\n<li>Can you apply Quicksort&#8217;s partitioning logic here?<\/li>\n<\/ul>\n<p><b>Solution<\/b> &#8211; This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a very useful divide-and-conquer based algorithm which rearranges the array such that the k<sup>th<\/sup> element is the k<sup>th<\/sup> smallest element in the array. A step-by-step version of Quickselect is \u2013<\/p>\n<div class=\"su-list su-list-style-\">\n<ul>\n<li>\u00a0Calculate the middle element for the given range.<\/li>\n<li><i class=\"fa fa-long-arrow-right\"><\/i> Place all the elements greater than the mid element to its right.<\/li>\n<li><i class=\"fa fa-long-arrow-right\"><\/i> Place all the elements lesser than the mid element to its left.<\/li>\n<li><i class=\"fa fa-long-arrow-right\"><\/i> If \u2018k\u2019 is less than the index of the middle element, then recursively call Quickselect on the left half of the range.<\/li>\n<li><i class=\"fa fa-long-arrow-right\"><\/i> If \u2018k\u2019 is greater than the index of the middle element, then recursively call Quickselect on the right half of the range.<\/li>\n<\/ul>\n<p><b>Code<\/b> &#8211;<\/p>\n<div class=\"su-tabs su-tabs-style-default su-tabs-mobile-stack\" data-active=\"1\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-tabs-nav\"><span class=\"\" data-url=\"\" data-target=\"blank\" tabindex=\"0\" role=\"button\">C<\/span><\/div><div class=\"su-tabs-panes\"><div class=\"su-tabs-pane su-u-clearfix su-u-trim\" data-title=\"C\">\n[code language=&#8221;cpp&#8221;]\n\/\/ Quick Select procedure to search for<br \/>\n\/\/ the kth smallest element in O(N) time.<br \/>\nvoid quickSelect(int arr[], int low, int high, int k)<br \/>\n{<br \/>\n    if (high &#8211; low &lt; k) {<br \/>\n        \/\/ A single element is<br \/>\n        \/\/ considered to be sorted<br \/>\n        return;<br \/>\n    }<\/p>\n<p>    int mid = low + ((high &#8211; low) \/ 2);<\/p>\n<p>    \/\/ Put the pivot at the last<br \/>\n    int temp = arr[mid];<br \/>\n    arr[mid] = arr[high];<br \/>\n    arr[high] = temp;<\/p>\n<p>    int pivot = arr[high];<br \/>\n    int i = low;<br \/>\n    int j = high &#8211; 1;<\/p>\n<p>    \/\/ The partition<br \/>\n    while (j &gt;= i) {<br \/>\n        if (arr[j] &lt; pivot &amp;&amp; arr[i] &gt; pivot) {<br \/>\n            temp = arr[i];<br \/>\n            arr[i] = arr[j];<br \/>\n            arr[j] = temp;<\/p>\n<p>            ++i;<br \/>\n            &#8211;j;<br \/>\n        } else if (arr[j] &lt; pivot &amp;&amp; arr[i] &lt;= pivot) {<br \/>\n            ++i;<br \/>\n        } else if (arr[j] &gt;= pivot &amp;&amp; arr[i] &gt; pivot) {<br \/>\n            &#8211;j;<br \/>\n        } else if (arr[j] &gt;= pivot &amp;&amp; arr[i] &lt;= pivot) {<br \/>\n            ++i;<br \/>\n            &#8211;j;<br \/>\n        }<br \/>\n    }<\/p>\n<p>    \/\/ Bring the pivot back to its<br \/>\n    \/\/ appropriate place<br \/>\n    temp = arr[i];<br \/>\n    arr[i] = arr[high];<br \/>\n    arr[high] = temp;<\/p>\n<p>    if (k &gt;= i) {<br \/>\n        quickSelect(arr, i + 1, high, k);<br \/>\n    } else {<br \/>\n        quickSelect(arr, low, i, k);<br \/>\n    }<br \/>\n}<br \/>\n[\/code]\n<\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an unsorted array of N elements, find the kth smallest element. This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[16],"tags":[20,22,61],"class_list":["post-3397","post","type-post","status-publish","format-standard","hentry","category-array-interview-questions","tag-arrays","tag-arrays-interview-questions","tag-interview-questions"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3397","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=3397"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3397\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=3397"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/categories?post=3397"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/tags?post=3397"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}