{"id":9296,"date":"2025-08-13T18:42:51","date_gmt":"2025-08-13T13:12:51","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=9296"},"modified":"2025-10-15T19:26:31","modified_gmt":"2025-10-15T13:56:31","slug":"last-stone-weight","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/last-stone-weight\/","title":{"rendered":"Last Stone Weight"},"content":{"rendered":"\n\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>You are given an array of integers <code>stones<\/code> where <code>stones[i]<\/code> is the weight of the <code>i<sup>th<\/sup><\/code> stone.<\/p> \n\n        <p>We are playing a game with the stones. On each turn, we choose the <strong>heaviest two stones<\/strong> and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:<\/p>\n\n        <ul>\n            <li>If <code>x == y<\/code>, both stones are destroyed, and<\/li>\n            <li>If <code>x != y<\/code>, the stone of weight x is destroyed, and the stone of weight <code>y<\/code> has new weight <code>y - x<\/code>.<\/li>\n        <\/ul>\n\n        <p>At the end of the game, there is <strong>at most one<\/strong> stone left.<\/p>\n\n        <p>Return <i>the weight of the last remaining stone<\/i>. If there are no stones left, return <code>0<\/code>.<\/p>\n                <h2>Examples:<\/h2>\n\n                <h5>Example 1:<\/h5>\n                <p><strong>Input:<\/strong>stones = [2,7,4,1,8,1]<\/p>\n                <p><strong>Output:<\/strong>1<\/p>\n                <p>\n                  <code>Explanation:<\/code>\n                  We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,\n                  we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,\n                  we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,\n                  we combine 1 and 1 to get 0 so the array converts to [1] then that&#8217;s the value of the last stone.\n                <\/p>\n\n                <h5>Example 2:<\/h5>\n                <p><strong>Input:<\/strong>stones = [1]<\/p>\n                <p><strong>Output:<\/strong>1<\/p>\n\n                    <h2>Constraints:<\/h2>\n                    <ul>\n                      <li><code>1 <= stones.length <= 30<\/code><\/li>\n                      <li><code>1 <= stones[i] <= 1000<\/code><\/li>\n                    <\/ul>\n\n                <h2>Approach<\/h2>\n                <ul>\n                   <li>Put all stones in a <strong>max-heap<\/strong> so the heaviest stones are always on top.<\/li> \n                   <li>While more than one stone remains:\n                    <ul>\n                        <li>Remove the two heaviest stones (<code>y<\/code> and <code>x<\/code>).<\/li>\n                        <li>If they are not equal, insert the difference (<code>y - x<\/code>) back into the heap.<\/li>\n                    <\/ul>\n                   <\/li>\n                   <li>Return the weight of the last stone, or <code>0<\/code> if none remain.<\/li>\n                <\/ul>\n\n                <h2>Time Complexity:<\/h2>\n                <li>\n                  <p><strong>Time Complexity = O(n * m)<\/strong>\n                  <\/li>\n                <h2>Space Complexity:<\/h2>\n                <li>\n                  <p><strong>Space Complexity = O(1)<\/strong><\/p>\n                <\/li>\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\nEnqueue 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\nExit 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<!-- <h2>Visualisation:<\/h2>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/07\/Screenshot-2025-07-16-at-9.54.46\u202fAM.png\" alt=\"Stocks\" \/> -->\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 lastStoneWeight = function(stones) {\n    let pq = new MaxPriorityQueue();\n    for(let i=0; i<stones.length; i++){\n        pq.enqueue(stones[i]);\n    }\n    while(pq.size() > 1){\n        let y = pq.dequeue();\n        let x = pq.dequeue();\n        if(y-x > 0){\n            pq.enqueue(y-x);\n        }\n    }\n    return pq.dequeue() || 0;\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\ndef lastStoneWeight(stones):\n    stones = [-s for s in stones]  # max heap by negating\n    heapq.heapify(stones)\n    while len(stones) > 1:\n        y = -heapq.heappop(stones)\n        x = -heapq.heappop(stones)\n        if y - x > 0:\n            heapq.heappush(stones, -(y - x))\n    return -stones[0] if stones else 0\nprint(lastStoneWeight([2,7,4,1,8,1]))\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\">\nimport java.util.*;\npublic class Main {\n    public static int lastStoneWeight(int[] stones) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());\n        for (int s : stones) pq.add(s);\n        while (pq.size() > 1) {\n            int y = pq.poll();\n            int x = pq.poll();\n            if (y - x > 0) {\n                pq.add(y - x);\n            }\n        }\n        return pq.isEmpty() ? 0 : pq.peek();\n    }\n    public static void main(String[] args) {\n        int[] stones = {2,7,4,1,8,1};\n        System.out.println(lastStoneWeight(stones));\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\">\nint lastStoneWeight(vector<int>& stones) {\n    priority_queue<int> pq(stones.begin(), stones.end());\n    while (pq.size() > 1) {\n        int y = pq.top(); pq.pop();\n        int x = pq.top(); pq.pop();\n        if (y - x > 0) {\n            pq.push(y - x);\n        }\n    }\n    return pq.empty() ? 0 : pq.top();\n}\nint main() {\n    vector<int> stones = {2,7,4,1,8,1};\n    cout << lastStoneWeight(stones) << endl;\n    return 0;\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\">\nvoid heapify(int arr[], int n, int i) {\n    int largest = i;\n    int left = 2*i + 1;\n    int right = 2*i + 2;\n    if (left < n &#038;&#038; arr[left] > arr[largest]) largest = left;\n    if (right < n &#038;&#038; arr[right] > arr[largest]) largest = right;\n    if (largest != i) {\n        int temp = arr[i];\n        arr[i] = arr[largest];\n        arr[largest] = temp;\n        heapify(arr, n, largest);\n    }\n}\nint extractMax(int arr[], int *n) {\n    if (*n == 0) return 0;\n    int maxVal = arr[0];\n    arr[0] = arr[*n - 1];\n    (*n)--;\n    heapify(arr, *n, 0);\n    return maxVal;\n}\nvoid insertHeap(int arr[], int *n, int val) {\n    arr[*n] = val;\n    (*n)++;\n    for (int i = (*n)\/2 - 1; i >= 0; i--) {\n        heapify(arr, *n, i);\n    }\n}\nint lastStoneWeight(int stones[], int size) {\n    for (int i = size\/2 - 1; i >= 0; i--) {\n        heapify(stones, size, i);\n    }\n    while (size > 1) {\n        int y = extractMax(stones, &size);\n        int x = extractMax(stones, &size);\n        if (y - x > 0) {\n            insertHeap(stones, &size, y - x);\n        }\n    }\n    return size == 0 ? 0 : stones[0];\n}\nint main() {\n    int stones[] = {2,7,4,1,8,1};\n    int size = sizeof(stones) \/ sizeof(stones[0]);\n    printf(\"%d\\n\", lastStoneWeight(stones, size));\n    return 0;\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\nclass Program {\n    public static int LastStoneWeight(int[] stones) {\n        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();\n        foreach (var s in stones) {\n            pq.Enqueue(s, -s); \/\/ negative for max-heap\n        }\n        while (pq.Count > 1) {\n            int y = pq.Dequeue();\n            int x = pq.Dequeue();\n            if (y - x > 0) {\n                pq.Enqueue(y - x, -(y - x));\n            }\n        }\n        return pq.Count == 0 ? 0 : pq.Dequeue();\n    }\n    static void Main() {\n        int[] stones = {2,7,4,1,8,1};\n        Console.WriteLine(LastStoneWeight(stones));\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","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x [4, 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":[210,322,260,176,175,211,811,174,172,173],"tags":[],"class_list":["post-9296","post","type-post","status-publish","format-standard","category-algorithms","category-algorithms-and-data-structures","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9296","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=9296"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9296\/revisions"}],"predecessor-version":[{"id":10355,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9296\/revisions\/10355"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=9296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=9296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=9296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}