{"id":9292,"date":"2025-08-13T16:29:15","date_gmt":"2025-08-13T10:59:15","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=9292"},"modified":"2025-10-15T19:43:26","modified_gmt":"2025-10-15T14:13:26","slug":"kth-smallest-element-in-a-sorted-matrix","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/kth-smallest-element-in-a-sorted-matrix\/","title":{"rendered":"Kth Smallest Element in a Sorted Matrix"},"content":{"rendered":"\n<!-- file - 13 -->\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\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    <div class=\"wp_blog_explanation\">\n        <h2>Problem Statement:<\/h2>\n\n        <p>Given an <code>n x n<\/code> <code>matrix<\/code> where each of the rows and columns is sorted in ascending order, return the <code>k<sup>th<\/sup><\/code> smallest element in the matrix.<\/p>\n        \n        <p>Note that it is the <code>k<sup>th<\/sup><\/code> smallest element in the sorted order, not the <code>k<sup>th<\/sup><\/code> distinct element.<\/p>\n\n        <p>You must find a solution with a memory complexity better than <code>O(n<sup>2<\/sup>)<\/code>.<\/p>\n        <h2>Examples:<\/h2>\n\n                <h3>Example 1:<\/h3>\n                <p><strong>Input:<\/strong> matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8<\/p>\n                <p><strong>Output:<\/strong>13<\/p>\n                <p><strong>Explanation:<\/strong> The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13<\/p>\n\n                <h3>Example 2:<\/h3>\n                <p><strong>Input:<\/strong>matrix = [[-5]], k = 1<\/p>\n                <p><strong>Output:<\/strong>-5<\/p>\n\n                    <h2>Constraints:<\/h2>\n                    <ul>\n                      <li><code>n == matrix.length == matrix[i].length<\/code><\/li>\n                      <li><code>1 <= n <= 300<\/code><\/li>\n                      <li><code>-10<sup>9<\/sup> <= matrix[i][j] <= 10<sup>9<\/sup><\/code>.<\/li>\n                      <li>It is <strong>guaranteed<\/strong> that the answer is <strong>unique<\/strong>.<\/li>\n                      <li>All the rows and columns of <code>matrix<\/code> are <strong>guaranteed<\/strong> to be sorted in <strong>non-decreasing order<\/strong>.<\/li>\n                      <li><code>1 <= k <= n<sup>2<\/sup><\/code><\/li>\n                    <\/ul>\n\n                    <h2>Approach<\/h2>\n                <ul>\n                    <li>Treat each <strong>row of the sorted matrix<\/strong> like a <code>sorted<\/code> list.<\/li>\n                    <li>Use a <code>min-heap<\/code> to <code>store the smallest available<\/code> element from each row.<\/li>\n                    <li>Initially, push the <strong>first element<\/strong> of each of the first <code>min(n, k)<\/code> rows into the heap.<\/li>\n                    <li>Repeatedly <strong>pop the smallest element<\/strong> from the heap and, if possible, push the next element from the same row.<\/li>\n                    <li>After popping <code>k-1 times<\/code>, the top of the heap is the <strong>k-th smallest element<\/strong>.<\/li>\n                <\/ul>\n\n                <h2>Time Complexity:<\/h2>\n                <li>\n                  <p><strong>Time Complexity = 0(min(n,k) log(min(n,k))) = O(n log n)<\/strong>\n                  <\/li>\n                <h2>Space Complexity:<\/h2>\n                <li>\n                  <p><strong>Space Complexity = 0(Min(n,k))<\/strong><\/p>\n                <\/li>\n\n<h2>Dry Run<\/h2>\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\n  <p><strong>Input:<\/strong> <code>stones = [2, 7, 4, 1, 8, 1]<\/code><\/p> \n  \n  <p><strong>State Transitions:<\/strong><\/p>\n  \n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\n\nStart Function lastStoneWeight([2, 7, 4, 1, 8, 1])\npq = new MaxPriorityQueue()\n\n-- Enqueue all stones --\ni = 0 \u2192 stones[0] = 2\n\u2192 pq.enqueue(2) \u2192 pq = [2]\n\ni = 1 \u2192 stones[1] = 7\n\u2192 pq.enqueue(7) \u2192 pq = [7, 2]\n\ni = 2 \u2192 stones[2] = 4\n\u2192 pq.enqueue(4) \u2192 pq = [7, 2, 4]\n\ni = 3 \u2192 stones[3] = 1\n\u2192 pq.enqueue(1) \u2192 pq = [7, 2, 4, 1]\n\ni = 4 \u2192 stones[4] = 8\n\u2192 pq.enqueue(8) \u2192 pq = [8, 7, 4, 2, 1]\n\ni = 5 \u2192 stones[5] = 1\n\u2192 pq.enqueue(1) \u2192 pq = [8, 7, 4, 2, 1, 1]\n\n-- Enter while loop (pq.size() > 1) --\nIteration 1:\n\u2192 y = pq.dequeue() -> 8\n\u2192 x = pq.dequeue() -> 7\n\u2192 y - x = 1  ( > 0 ) \u2192 pq.enqueue(1)\npq after enqueue -> [4, 2, 1, 1, 1]\n\nIteration 2:\n\u2192 y = pq.dequeue() -> 4\n\u2192 x = pq.dequeue() -> 2\n\u2192 y - x = 2  ( > 0 ) \u2192 pq.enqueue(2)\npq after enqueue -> [2, 1, 1, 1, 2]  (equivalently [2, 2, 1, 1, 1])\n\nIteration 3:\n\u2192 y = pq.dequeue() -> 2\n\u2192 x = pq.dequeue() -> 2\n\u2192 y - x = 0  (== 0) \u2192 do NOT enqueue\npq after removals -> [1, 1, 1]\n\nIteration 4:\n\u2192 y = pq.dequeue() -> 1\n\u2192 x = pq.dequeue() -> 1\n\u2192 y - x = 0  (== 0) \u2192 do NOT enqueue\npq after removals -> [1]\n\n-- Exit while (pq.size() == 1) --\nReturn pq.dequeue() || 0 -> returns 1\n  <\/pre> \n  \n  <p><strong>Final Output:<\/strong> <code>1<\/code><\/p> \n  <p><strong>Explanation:<\/strong> repeatedly smash the two largest stones; after all smashes one stone of weight <code>1<\/code> remains, so the function returns <code>1<\/code>.<\/p> \n<\/div>\n\n\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        <!-- JavaScript -->\n        <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n            <pre><code class=\"language-javascript\">\nvar kthSmallest = function(matrix, k) {\n    let n = matrix[0].length;\n    let heap = new MinPriorityQueue(x => x.val);\n    for(let i = 0; i < Math.min(n,k); i++) {\n        heap.push({val: matrix[i][0], row: i, col: 0});\n    }\n    for(let count=0; count < k-1; count++) {\n        let {val, row, col} = heap.pop();\n        if(col+1 < n) {\n            heap.push({val: matrix [row][col+1], row: row, col: col+1});\n        }\n    }\n    return heap.pop().val;\n};\n     <\/code><\/pre>\n        <\/div>\n\n        <!-- Python -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n            <pre><code class=\"language-python\">\nimport heapq\n\ndef kthSmallest(matrix, k):\n    n = len(matrix)\n    heap = []\n    \n    for i in range(min(n, k)):\n        heapq.heappush(heap, (matrix[i][0], i, 0))\n    \n    for _ in range(k - 1):\n        val, row, col = heapq.heappop(heap)\n        if col + 1 < n:\n            heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))\n    return heapq.heappop(heap)[0]\n            <\/code><\/pre>\n        <\/div>\n\n        <!-- Java -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n            <pre><code class=\"language-java\">\nclass Solution {\n    static class Node {\n        int val, row, col;\n        Node(int v, int r, int c) {\n            val = v; row = r; col = c;\n        }\n    }\n\n    public int kthSmallest(int[][] matrix, int k) {\n        int n = matrix.length;\n        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.val - b.val);\n\n        for (int i = 0; i < Math.min(n, k); i++) {\n            pq.offer(new Node(matrix[i][0], i, 0));\n        }\n\n        for (int count = 0; count < k - 1; count++) {\n            Node top = pq.poll();\n            if (top.col + 1 < n) {\n                pq.offer(new Node(matrix[top.row][top.col + 1], top.row, top.col + 1));\n            }\n        }\n        return pq.poll().val;\n    }\n}\n      <\/code><\/pre>\n        <\/div>\n\n        <!-- C++ -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n            <pre><code class=\"language-cpp\">\nstruct Node {\n    int val, row, col;\n    bool operator>(const Node &other) const {\n        return val > other.val;\n    }\n};\nint kthSmallest(vector<vector<int>>& matrix, int k) {\n    int n = matrix.size();\n    priority_queue<Node, vector<Node>, greater<Node>> minHeap;\n\n    for (int i = 0; i < min(n, k); i++) {\n        minHeap.push({matrix[i][0], i, 0});\n    }\n    for (int count = 0; count < k - 1; count++) {\n        Node top = minHeap.top();\n        minHeap.pop();\n        if (top.col + 1 < n) {\n            minHeap.push({matrix[top.row][top.col + 1], top.row, top.col + 1});\n        }\n    }\n    return minHeap.top().val;\n} <\/code><\/pre>\n        <\/div>\n\n        <!-- C -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n            <pre><code class=\"language-c\">\ntypedef struct {\n    int val, row, col;\n} Node;\nvoid swap(Node* a, Node* b) {\n    Node temp = *a; *a = *b; *b = temp;\n}\n\nvoid heapify(Node heap[], int n, int i) {\n    int smallest = i, l = 2*i + 1, r = 2*i + 2;\n    if (l < n &#038;&#038; heap[l].val < heap[smallest].val) smallest = l;\n    if (r < n &#038;&#038; heap[r].val < heap[smallest].val) smallest = r;\n    if (smallest != i) {\n        swap(&#038;heap[i], &#038;heap[smallest]);\n        heapify(heap, n, smallest);\n    }\n}\nint kthSmallest(int** matrix, int n, int k) {\n    Node heap[k];\n    int size = 0;\n    for (int i = 0; i < (n < k ? n : k); i++) {\n        heap[size++] = (Node){matrix[i][0], i, 0};\n    }\n    for (int i = size \/ 2 - 1; i >= 0; i--) heapify(heap, size, i);\n    for (int count = 0; count < k - 1; count++) {\n        Node top = heap[0];\n        if (top.col + 1 < n) {\n            heap[0] = (Node){matrix[top.row][top.col + 1], top.row, top.col + 1};\n        } else {\n            heap[0] = heap[size - 1];\n            size--;\n        }\n        heapify(heap, size, 0);\n    }\n    return heap[0].val;\n}     <\/code><\/pre>\n        <\/div>\n\n        <!-- C# -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n            <pre><code class=\"language-csharp\">\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n    public class Node {\n        public int val, row, col;\n        public Node(int v, int r, int c) { val = v; row = r; col = c; }\n    }\n\n    public int KthSmallest(int[][] matrix, int k) {\n        int n = matrix.Length;\n        var pq = new PriorityQueue<Node, int>();\n\n        for (int i = 0; i < Math.Min(n, k); i++) {\n            pq.Enqueue(new Node(matrix[i][0], i, 0), matrix[i][0]);\n        }\n\n        for (int count = 0; count < k - 1; count++) {\n            var top = pq.Dequeue();\n            if (top.col + 1 < n) {\n                pq.Enqueue(new Node(matrix[top.row][top.col + 1], top.row, top.col + 1),\n                           matrix[top.row][top.col + 1]);\n            }\n        }\n        return pq.Dequeue().val;\n    }\n}\n        <\/code><\/pre>\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\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with a memory complexity<\/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":[210,260,176,175,211,810,174,172,173],"tags":[],"class_list":{"0":"post-9292","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-algorithms","7":"category-c-c-plus-plus","8":"category-csharp","9":"category-cplusplus","10":"category-data-structures","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\/9292","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=9292"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9292\/revisions"}],"predecessor-version":[{"id":10361,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9292\/revisions\/10361"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=9292"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=9292"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=9292"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}