{"id":9251,"date":"2025-08-12T16:50:36","date_gmt":"2025-08-12T11:20:36","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=9251"},"modified":"2025-10-15T18:23:45","modified_gmt":"2025-10-15T12:53:45","slug":"kth-largest-element-in-an-array","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/kth-largest-element-in-an-array\/","title":{"rendered":"Kth Largest Element in an Array"},"content":{"rendered":"\n<!-- Evaluate Reverse Polish Notation 10-->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n<div class=\"wp_blog_container wp_blog_theme\">\n<button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n<h1 class=\"wp_blog_main-heading\"><\/h1>\n\n<div class=\"wp_blog_explanation\">\n    \n    <h2>Problem Statement:<\/h2>\n    <p>Given an integer array nums and an integer <code>k<sup>th<\/sup><\/code>, return <i>the <code>k<sup>th<\/sup><\/code> largest element in the array<\/i>.<\/p>\n\n    <p>Note that it is the <code>k<sup>th<\/sup><\/code> largest element in the sorted order, not the <code>k<sup>th<\/sup><\/code> distinct element.<\/p>\n    \n    <p>Can you solve it without sorting?<\/p>\n\n    <p><strong>Example 1:<\/strong><\/p>\n    <p><strong>Input:<\/strong><\/p>\n        <p>nums = [3,2,1,5,6,4], k = 2<\/p>\n    <p><strong>Output:<\/strong><code>5<\/code><\/p>\n\n    <p><strong>Example 2:<\/strong><\/p>\n    <p><strong>Input:<\/strong><\/p>\n        <p>nums = [3,2,3,1,2,4,5,5,6], k = 4<\/p>\n    <p><strong>Output:<\/strong><code>4<\/code><\/p>\n\n    <h2>Constraints:<\/h2>\n    <ul>\n        <li><code>1 <= k <= nums.length <= 10<sup>5<\/sup><\/code><\/li>\n        <li><code>-10<sup>4<\/sup> <= nums[i] <= 10<sup>4<\/sup><\/code><\/li>\n    <\/ul>\n\n    <h2>Approach:<\/h2>\n   <ul>\n    <li>Use a <strong>min-heap<\/strong> to store the largest <code>k<\/code> elements.<\/li>\n    <li>Traverse each number in <code>nums<\/code> and push it into the heap.<\/li>\n    <li>If the heap size exceeds <code>k<\/code>, remove the smallest element (heap root).<\/li>\n    <li>After processing all elements, the heap\u2019s top (smallest in the heap) will be the <strong>k-th largest<\/strong> in the array.<\/li>\n   <\/ul> \n\n    <h2>Time Complexity:<\/h2>\n    <li><p><strong>Time Complexity = O(n log k)<\/strong><\/p><\/li> \n    <h2>Space Complexity:<\/h2>\n    <li><p><strong>Space Complexity = O(K)<\/strong><\/p><\/li>\n\n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\"> \n  <p><strong>Input:<\/strong> nums = [3, 2, 1, 5, 6, 4] k = 2<\/p>\n    <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\n  <p><strong>State Transitions:<\/strong><\/p>\n  <pre>\nInitialize: pq = MinPriorityQueue()\n\ni = 0 \u2192 nums[0] = 3\n\u2192 pq.enqueue(3) \u2192 pq = [3]\n\ni = 1 \u2192 nums[1] = 2\n\u2192 pq.enqueue(2) \u2192 pq = [2, 3]  (min-heap: 2 is root)\n\ni = 2 \u2192 nums[2] = 1\n\u2192 pq.enqueue(1) \u2192 pq = [1, 3, 2]\n\u2192 pq.size() = 3 > k (2) \u2192 pq.dequeue() removes smallest (1)\n\u2192 pq = [2, 3]\n\ni = 3 \u2192 nums[3] = 5\n\u2192 pq.enqueue(5) \u2192 pq = [2, 3, 5]\n\u2192 pq.size() = 3 > k \u2192 pq.dequeue() removes smallest (2)\n\u2192 pq = [3, 5]\n\ni = 4 \u2192 nums[4] = 6\n\u2192 pq.enqueue(6) \u2192 pq = [3, 5, 6]\n\u2192 pq.size() = 3 > k \u2192 pq.dequeue() removes smallest (3)\n\u2192 pq = [5, 6]\n\ni = 5 \u2192 nums[5] = 4\n\u2192 pq.enqueue(4) \u2192 pq = [4, 6, 5]\n\u2192 pq.size() = 3 > k \u2192 pq.dequeue() removes smallest (4)\n\u2192 pq = [5, 6]\n  <\/pre>\n  <p><strong>Final Output:<\/strong> <code>5<\/code><\/p>\n  <p><strong>Explanation:<\/strong> pq.front() returns the smallest in the heap \u2192 the 2nd largest element overall.<\/p>\n<\/div>\n<\/div>\n\n<div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n        <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n<pre><code class=\"language-javascript\">\nvar findKthLargest = function(nums, k) {\n    let pq = new MinPriorityQueue();\n    for(let i=0; i<nums.length; i++){\n        pq.enqueue(nums[i]);\n        if(pq.size() > k) {\n            pq.dequeue();\n        }\n    }\n    return pq.front();\n};\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n<pre><code class=\"language-python\">\nimport heapq\ndef findKthLargest(nums, k):\n    pq = []\n    for num in nums:\n        heapq.heappush(pq, num)\n        if len(pq) > k:\n            heapq.heappop(pq)\n    return pq[0]\nnums = [3, 2, 1, 5, 6, 4]\nk = 2\nprint(findKthLargest(nums, k))\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n<pre><code class=\"language-java\">\nimport java.util.*;\npublic class Main {\n    public static int findKthLargest(int[] nums, int k) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>();\n        for (int num : nums) {\n            pq.add(num);\n            if (pq.size() > k) {\n                pq.poll();\n            }\n        }\n        return pq.peek();\n    }\n    public static void main(String[] args) {\n        int[] nums = {3, 2, 1, 5, 6, 4};\n        int k = 2;\n        System.out.println(findKthLargest(nums, k));\n    }\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n<pre><code class=\"language-cpp\">\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;queue&gt;\nusing namespace std;\nint findKthLargest(vector<int>& nums, int k) {\n    priority_queue<int, vector<int>, greater<int>> pq;\n    for (int num : nums) {\n        pq.push(num);\n        if (pq.size() > k) {\n            pq.pop();\n        }\n    }\n    return pq.top();\n}\nint main() {\n    vector<int> nums = {3, 2, 1, 5, 6, 4};\n    int k = 2;\n    cout << findKthLargest(nums, k) << endl;\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n<pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\nvoid heapify(int heap[], int n, int i) {\n    int smallest = i;\n    int left = 2*i + 1;\n    int right = 2*i + 2;\n    if (left < n &#038;&#038; heap[left] < heap[smallest]) smallest = left;\n    if (right < n &#038;&#038; heap[right] < heap[smallest]) smallest = right;\n    if (smallest != i) {\n        int temp = heap[i];\n        heap[i] = heap[smallest];\n        heap[smallest] = temp;\n        heapify(heap, n, smallest);\n    }\n}\nvoid pushHeap(int heap[], int *size, int val) {\n    heap[(*size)++] = val;\n    for (int i = (*size)\/2 - 1; i >= 0; i--) {\n        heapify(heap, *size, i);\n    }\n}\nvoid popHeap(int heap[], int *size) {\n    heap[0] = heap[--(*size)];\n    for (int i = (*size)\/2 - 1; i >= 0; i--) {\n        heapify(heap, *size, i);\n    }\n}\nint findKthLargest(int nums[], int n, int k) {\n    int heap[100];\n    int size = 0;\n    for (int i = 0; i < n; i++) {\n        pushHeap(heap, &#038;size, nums[i]);\n        if (size > k) {\n            popHeap(heap, &size);\n        }\n    }\n    return heap[0];\n}\nint main() {\n    int nums[] = {3, 2, 1, 5, 6, 4};\n    int k = 2;\n    int n = sizeof(nums) \/ sizeof(nums[0]);\n    printf(\"%d\\n\", findKthLargest(nums, n, k));\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n<pre><code class=\"language-csharp\">\nusing System;\nusing System.Collections.Generic;\nclass Program {\n    static int FindKthLargest(int[] nums, int k) {\n        var pq = new PriorityQueue<int, int>();\n        foreach (var num in nums) {\n            pq.Enqueue(num, num);\n            if (pq.Count > k) {\n                pq.Dequeue();\n            }\n        }\n        return pq.Peek();\n    }\n    static void Main() {\n        int[] nums = { 3, 2, 1, 5, 6, 4 };\n        int k = 2;\n        Console.WriteLine(FindKthLargest(nums, k));\n    }\n}\n<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: Given an integer array nums and an integer kth, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting? Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output:5 Example 2:<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[260,176,175,211,811,810,174,172,173],"tags":[],"class_list":{"0":"post-9251","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-c-c-plus-plus","7":"category-csharp","8":"category-cplusplus","9":"category-data-structures","10":"category-data-structures-and-algorithms","11":"category-dsa","12":"category-java","13":"category-javascript","14":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9251","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=9251"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9251\/revisions"}],"predecessor-version":[{"id":10351,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9251\/revisions\/10351"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=9251"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=9251"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=9251"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}