{"id":900,"date":"2023-12-11T13:00:00","date_gmt":"2023-12-11T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=900"},"modified":"2023-12-13T05:35:38","modified_gmt":"2023-12-13T05:35:38","slug":"kth-largest-element","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/kth-largest-element\/","title":{"rendered":"Find Kth Largest Element in an Array (C++, Java, Python)"},"content":{"rendered":"\n<p>One of the array problems that is commonly asked in technical interviews is finding the kth largest element in the array. It becomes more challenging when we have to solve it without sorting, in this article we will discuss the optimal approach to solve this problem with implementation in C++, Java, and Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is kth Largest Element Problem?<\/strong><\/h2>\n\n\n\n<p>In this <a href=\"https:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/\" target=\"_blank\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a>, we have to find the kth largest element in an array, an element that comes in the kth place of the largest element where k is given.<\/p>\n\n\n\n<p>Let us understand it with an example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\">Array = [7,4,2,5,3,1]<br>K = 3<br>Output = 4<\/p>\n\n\n\n<p>The 1st largest is 7, 2nd largest is 5, and the 3rd largest, i.e. the kth largest is 4.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"152\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6-1024x152.png\" alt=\"Example of Kth Largest Element Problem\" class=\"wp-image-906\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6-1024x152.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6-300x45.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6-768x114.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6-750x111.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6-1140x169.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-6.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimal Approach using Min-Heap<\/strong><\/h2>\n\n\n\n<p><strong>To find the Kth Largest Element in an Array without sorting we have to use a min-heap and maintain it with size k.<\/strong><\/p>\n\n\n\n<p>Here are the steps involved:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In the first step, we must declare a priority queue with greater&lt;int&gt;. The greater&lt;int&gt; is a custom comparator that ensures the smallest element on the top.<br><\/li>\n\n\n\n<li>Now we will iterate through the array and insert each element into the min-heap. We will keep a check that if the size of the min-heap exceeds k then we will remove the smallest element (root) of the min-heap.<br>\n<ul class=\"wp-block-list\">\n<li>Firstly we will insert 7, 4, 2, and 5 and our min-heap will look like this:<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/i4lCB45lN7xNQFwgFPu-UZkXjlwr-bARUOKH1ceWXg8b3dVHwEzBN2hXY7kbcgAPP_iR-KGIrkk9vwffEVAVmyFuZf65wavle0PW-Rgbl96bVkWuE2EmCT1H1oYKkRAILDq_2p1v7aWt8uBAYR4cOKo\" alt=\"Insert all the elements in heap\" style=\"aspect-ratio:0.9861111111111112;width:312px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now after this min-heap will check that size if the size is greater than k then pop an element<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"400\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10-1024x400.png\" alt=\"Pop an element\" class=\"wp-image-910\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10-1024x400.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10-300x117.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10-768x300.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10-750x293.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10-1140x445.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-10.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now again an element is inserted in the min-heap<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"375\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3-1024x375.png\" alt=\"Insert 3 in heap\" class=\"wp-image-911\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3-1024x375.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3-300x110.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3-768x281.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3-750x274.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3-1140x417.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-3.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Again min-heap size increased than the k size so we will pop an element<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"400\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11-1024x400.png\" alt=\"Pop an element\" class=\"wp-image-912\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11-1024x400.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11-300x117.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11-768x300.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11-750x293.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11-1140x445.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-11.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now 1 is inserted in min-heap<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"384\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5-1024x384.png\" alt=\"Inserting 1 in heap\" class=\"wp-image-913\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5-1024x384.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5-300x113.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5-768x288.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5-750x281.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5-1140x428.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-5.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Again min-heap size increased than the k size so we will pop an element and now all elements are iterated once and we have maintained a min heap of size k.<br><\/li>\n\n\n\n<li>So the root of our min-heap is our kth largest element.<br><\/li>\n\n\n\n<li>After doing the above step for elements present in the array we will get a min heap of k size and the root of the min-heap is our kth largest element<\/li>\n<\/ul>\n\n\n\n<p>For example, if we have n number of elements and we have to give nth largest element then we have to return the smallest element present in the array as the same thing we are doing by maintaining k size min-heap.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is a C++ program to find the Kth largest element in an array:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint findKthLargest(vector&lt;int&gt;&amp; nums, int k) {\n    \/\/ Create a min-heap\n    priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; minHeap;\n\n    \/\/ Insert elements into the heap until size reaches k\n    for (int num : nums) {\n        minHeap.push(num);\n        if (minHeap.size() &gt; k) {\n            minHeap.pop();  \/\/ Maintain size of k\n        }\n    }\n\n    \/\/ The root of the max-heap is the kth largest element\n    return minHeap.top();\n}\n\nint main() {\n    vector&lt;int&gt; nums = {7, 4, 2 , 5, 3, 1};\n    int k = 3;\n\n    int result = findKthLargest(nums, k);\n\n    cout &lt;&lt; &quot;The &quot; &lt;&lt; k &lt;&lt; &quot;th largest element is: &quot; &lt;&lt; result &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Here is a Python program as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">import heapq\n\ndef find_kth_largest(nums, k):\n    min_heap = []\n\n    for num in nums:\n        heapq.heappush(min_heap, num)\n        if len(min_heap) &gt; k:\n            heapq.heappop(min_heap)\n\n    return min_heap[0]\n\n# Example usage\nnums = [7, 4, 2, 5, 3, 1]\nk = 3\nresult = find_kth_largest(nums, k)\nprint(f&quot;The {k}th largest element is: {result}&quot;)<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>You can implement it in Java for Min-Heap approach also:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.PriorityQueue;\n\npublic class KthLargestElement {\n    public static int findKthLargest(int[] nums, int k) {\n        \/\/ Create a min-heap\n        PriorityQueue&lt;Integer&gt; minHeap = new PriorityQueue&lt;&gt;();\n\n        \/\/ Insert elements into the heap until size reaches k\n        for (int num : nums) {\n            minHeap.offer(num);\n            if (minHeap.size() &gt; k) {\n                minHeap.poll(); \/\/ Maintain size of k\n            }\n        }\n\n        \/\/ The root of the max-heap is the kth largest element\n        return minHeap.peek();\n    }\n\n    public static void main(String[] args) {\n        int[] nums = {7, 4, 2, 5, 3, 1};\n        int k = 3;\n\n        int result = findKthLargest(nums, k);\n\n        System.out.println(&quot;The &quot; + k + &quot;th largest element is: &quot; + result);\n    }\n}<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>The 3th largest element is: 4<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Complexity Analysis<\/strong><\/h3>\n\n\n\n<p>The time complexity for this is O(n*logK) where n is the size of an array and k is the element we have to return. Firstly we are iterating through arrays and inserting elements in a min-heap.<\/p>\n\n\n\n<p>The space complexity is O(k) because the space used by the min-heap is of k size only in the worst case if k = n then space complexity is equal to O(k).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In this article, we have learned that the min-heap-based approach provides an efficient solution for finding the kth largest element without explicitly sorting the entire array. It is particularly beneficial when k is significantly smaller than the size of the array, optimizing both time and space complexity. <\/p>\n\n\n\n<p>There are many other array problems you might have to practice, and if you face any hurdle, our <a href=\"https:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/\" target=\"_blank\" rel=\"noopener\">data structures tutors<\/a> are available 24&#215;7 online!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We will the leetcode problem of finding the kth largest element in an array using min heap approach with time and space complexities.<\/p>\n","protected":false},"author":12,"featured_media":902,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-900","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/900","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=900"}],"version-history":[{"count":6,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/900\/revisions"}],"predecessor-version":[{"id":954,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/900\/revisions\/954"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/902"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=900"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=900"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=900"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}