{"id":7783,"date":"2025-07-11T16:06:06","date_gmt":"2025-07-11T10:36:06","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=7783"},"modified":"2025-07-11T16:09:00","modified_gmt":"2025-07-11T10:39:00","slug":"rotting-oranges","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/rotting-oranges\/","title":{"rendered":"Rotting Oranges"},"content":{"rendered":"\n<!-- Next Greater Element I -->\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: #f8c291;\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    \/* 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    .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    .wp_blog_explanation code {\n        background: #fef9f4;\n        padding: 3px 6px;\n        border-radius: 4px;\n        font-family: \"Courier New\", monospace;\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    .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    .wp_blog_code-tab-button:hover {\n        background: var(--secondary);\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    .wp_blog_code-tab-content.active {\n        display: block;\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<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n<h1 class=\"wp_blog_main-heading\"><\/h1>\n\n<div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n    <p>\n        You are given an <code>m x n<\/code> grid where each cell can have one of three values:\n    <\/p>\n    <p>\n        <ul>\n            <li><code>0<\/code> representing an empty cell,<\/li>\n            <li><code>1<\/code> representing a fresh orange, or<\/li>\n            <li><code>2<\/code> representing a rotten orange.<\/li>\n        <\/ul>\n    <\/p>\n\n    <p>Every minute, any fresh orange that is <strong>4-directionally adjacent<\/strong> to a rotten orange becomes rotten.<\/p>\n    \n    <p>Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return <code>-1<\/code>.<\/p>\n\n\n    <h2>Examples:<\/h2>\n    <p><strong>Example 1:<\/strong><\/p>\n    <p><strong>Input:<\/strong><\/p>\n        <p>grid = [[2,1,1],[0,1,1],[1,0,1]]<\/p>\n    <p><strong>Output:<\/strong><code> -1<\/code><\/p>\n    <p><strong>Explanation:<\/strong> The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.<\/p>\n\n    <p><strong>Example 2:<\/strong><\/p>\n    <p><strong>Input:<\/strong><\/p>\n        <p>grid = [[0,2]]<\/p>\n    <p><strong>Output:<\/strong><code> 0<\/code><\/p>\n    <p><strong>Explanation:<\/strong> Since there are already no fresh oranges at minute 0, the answer is just 0.<\/p>\n    \n    <p><strong>For more details, refer to LeetCode problem 994.<\/strong><\/p>\n\n    <h2>Constraints:<\/h2>\n    <ul>\n        <li><code>m == grid.length<\/code><\/li>\n        <li><code>n == grid[i].length<\/code><\/li>\n        <li><code>1 <= m, n <= 10<\/code><\/li>\n        <li><code>grid[i][j] is 0, 1, or 2.<\/code><\/li>\n    <\/ul>\n\n    <h2>Approach:<\/h2>\n    <ul>\n        <li><strong>Identify rotten oranges<\/strong> (2) and push their positions + time <code>([i, j, 0])<\/code> into a <strong>queue<\/strong>.<\/li>\n        \n        <li><strong>Use BFS<\/strong> to spread rot in 4 directions (up, down, left, right).\n            <ul>\n                <li>For each direction:\n                    If neighbor is a fresh orange (1), rot it (\u2192 2) and push it into the queue with time +1.\n                <\/li>\n            <\/ul>\n        <\/li>\n\n        <li><strong>Track time<\/strong> with <code>maxMinutes<\/code>.<\/li>\n    \n        <li>After BFS, if any fresh orange <code>(1)<\/code> left, return <code>-1<\/code>.<\/li>\n        <li>Else, return <code>maxMinutes<\/code>.<\/li>\n    <\/ul>\n\n    <h2>Visualisation:<\/h2>\n    <img decoding=\"async\"\n        src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/07\/Screenshot-2025-07-11-at-3.59.21\u202fPM.png\"\n        alt=\"stack\"\n    \/>\n                <h2>Time Complexity:<\/h2>\n                <li>\n                  <p><strong>Time Complexity = O(m x n)<\/strong> \n                <\/li> \n                <h2>Space Complexity:<\/h2>\n                <li>\n                  <p><strong>Space Complexity = O(m x n)<\/strong> \n                <\/p>\n                <\/li>\n\n<h2>Dry Run<\/h2> <div style=\"background: #f9f9f9; border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0;\"> <p><strong>Input:<\/strong><\/p> <pre style=\"white-space: pre-wrap; background: #fff5ea; padding: 1rem; border-radius: 8px; overflow-x: auto;\"> grid = [ [2,1,1], [1,1,0], [0,1,1] ] <\/pre> <p><strong>State Transitions:<\/strong><\/p> <pre style=\"white-space: pre-wrap; background: #fff5ea; padding: 1rem; border-radius: 8px; overflow-x: auto;\"> Initialize: m = 3, n = 3 queue = []\n\u2192 Scanning grid:\nFound rotten orange at (0,0) \u2192 queue = [[0,0,0]]\n\nStart BFS:\nqueue = [[0,0,0]]\nmaxMinutes = 0\n\nPop [0,0,0]\n\u2192 (0,1) is fresh \u2192 rot it \u2192 queue.push([0,1,1])\n\u2192 (1,0) is fresh \u2192 rot it \u2192 queue.push([1,0,1])\nmaxMinutes = max(0, 0) = 0\n\nPop [0,1,1]\n\u2192 (0,2) is fresh \u2192 rot it \u2192 queue.push([0,2,2])\n\u2192 (1,1) is fresh \u2192 rot it \u2192 queue.push([1,1,2])\nmaxMinutes = max(1, 0) = 1\n\nPop [1,0,1]\n\u2192 (2,0) is 0 (empty) \u2192 skip\nmaxMinutes = max(1, 1) = 1\n\nPop [0,2,2]\n\u2192 (1,2) is 0 \u2192 skip\nmaxMinutes = max(2, 1) = 2\n\nPop [1,1,2]\n\u2192 (2,1) is fresh \u2192 rot it \u2192 queue.push([2,1,3])\nmaxMinutes = max(2, 2) = 2\n\nPop [2,1,3]\n\u2192 (2,2) is fresh \u2192 rot it \u2192 queue.push([2,2,4])\nmaxMinutes = max(3, 2) = 3\n\nPop [2,2,4]\n\u2192 all neighbors are either 0 or already rotten\nmaxMinutes = max(4, 3) = 4\n\n\u2192 BFS finished, check for any remaining fresh oranges:\n\u2192 All are rotten or empty\n\n<\/pre> <p><strong>Final Output:<\/strong> <code>4<\/code><\/p> <p><strong>Final State:<\/strong> <code> grid = [ [2,2,2], [2,2,0], [0,2,2] ]<\/code> <\/p> <\/div>\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\">\n            JavaScript\n        <\/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 orangesRotting = function(grid) {\n    let m = grid.length;\n    let n = grid[0].length;\n    let queue = [];\n    for (let i = 0; i < m; i++) {\n        for (let j = 0; j < n; j++) {\n            if (grid[i][j] === 2) {\n                queue.push([i, j, 0]);\n            }\n        }\n    }\n    let maxMinutes = 0;\n    while (queue.length) {\n        let [x, y, level] = queue.shift();\n\n        if (x > 0 && grid[x - 1][y] === 1) {\n            grid[x - 1][y] = 2;\n            queue.push([x - 1, y, level + 1]);\n        }\n        if (x < m - 1 &#038;&#038; grid[x + 1][y] === 1) {\n            grid[x + 1][y] = 2;\n            queue.push([x + 1, y, level + 1]);\n        }\n        if (y < n - 1 &#038;&#038; grid[x][y + 1] === 1) {\n            grid[x][y + 1] = 2;\n            queue.push([x, y + 1, level + 1]);\n        }\n        if (y > 0 && grid[x][y - 1] === 1) {\n            grid[x][y - 1] = 2;\n            queue.push([x, y - 1, level + 1]);\n        }\n        maxMinutes = Math.max(level, maxMinutes);\n    }\n    for (let i = 0; i < m; i++) {\n        for (let j = 0; j < n; j++) {\n            if (grid[i][j] === 1) {\n                return -1;\n            }\n        }\n    }\n    return maxMinutes;\n};\n<\/code>\n<\/pre>\n<\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n        <pre><code class=\"language-python\">\nfrom collections import deque\ndef orangesRotting(grid):\n    m = len(grid)\n    n = len(grid[0])\n    queue = deque()\n    for i in range(m):\n        for j in range(n):\n            if grid[i][j] == 2:\n                queue.append((i, j, 0))\n    maxMinutes = 0\n    while queue:\n        x, y, level = queue.popleft()\n\n        if x > 0 and grid[x - 1][y] == 1:\n            grid[x - 1][y] = 2\n            queue.append((x - 1, y, level + 1))\n        if x < m - 1 and grid[x + 1][y] == 1:\n            grid[x + 1][y] = 2\n            queue.append((x + 1, y, level + 1))\n        if y < n - 1 and grid[x][y + 1] == 1:\n            grid[x][y + 1] = 2\n            queue.append((x, y + 1, level + 1))\n        if y > 0 and grid[x][y - 1] == 1:\n            grid[x][y - 1] = 2\n            queue.append((x, y - 1, level + 1))\n        maxMinutes = max(maxMinutes, level)\n    for row in grid:\n        if 1 in row:\n            return -1\n    return maxMinutes\n    <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n        <pre><code class=\"language-java\">\npublic int orangesRotting(int[][] grid) {\n    int m = grid.length;\n    int n = grid[0].length;\n    Queue<int[]> queue = new LinkedList<>();\n    for (int i = 0; i < m; i++) {\n        for (int j = 0; j < n; j++) {\n            if (grid[i][j] == 2) {\n                queue.add(new int[]{i, j, 0});\n            }\n        }\n    }\n    int maxMinutes = 0;\n    while (!queue.isEmpty()) {\n        int[] curr = queue.poll();\n        int x = curr[0], y = curr[1], level = curr[2];\n\n        if (x > 0 && grid[x - 1][y] == 1) {\n            grid[x - 1][y] = 2;\n            queue.add(new int[]{x - 1, y, level + 1});\n        }\n        if (x < m - 1 &#038;&#038; grid[x + 1][y] == 1) {\n            grid[x + 1][y] = 2;\n            queue.add(new int[]{x + 1, y, level + 1});\n        }\n        if (y < n - 1 &#038;&#038; grid[x][y + 1] == 1) {\n            grid[x][y + 1] = 2;\n            queue.add(new int[]{x, y + 1, level + 1});\n        }\n        if (y > 0 && grid[x][y - 1] == 1) {\n            grid[x][y - 1] = 2;\n            queue.add(new int[]{x, y - 1, level + 1});\n        }\n        maxMinutes = Math.max(level, maxMinutes);\n    }\n    for (int i = 0; i < m; i++) {\n        for (int j = 0; j < n; j++) {\n            if (grid[i][j] == 1) return -1;\n        }\n    }\n    return maxMinutes;\n}\n <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n        <pre><code class=\"language-cpp\">\nint orangesRotting(vector<vector<int>>& grid) {\n    int m = grid.size();\n    int n = grid[0].size();\n    queue<tuple<int, int, int>> q;\n    for (int i = 0; i < m; ++i) {\n        for (int j = 0; j < n; ++j) {\n            if (grid[i][j] == 2) {\n                q.push({i, j, 0});\n            }\n        }\n    }\n    int maxMinutes = 0;\n    while (!q.empty()) {\n        auto [x, y, level] = q.front();\n        q.pop();\n\n        if (x > 0 && grid[x - 1][y] == 1) {\n            grid[x - 1][y] = 2;\n            q.push({x - 1, y, level + 1});\n        }\n        if (x < m - 1 &#038;&#038; grid[x + 1][y] == 1) {\n            grid[x + 1][y] = 2;\n            q.push({x + 1, y, level + 1});\n        }\n        if (y < n - 1 &#038;&#038; grid[x][y + 1] == 1) {\n            grid[x][y + 1] = 2;\n            q.push({x, y + 1, level + 1});\n        }\n        if (y > 0 && grid[x][y - 1] == 1) {\n            grid[x][y - 1] = 2;\n            q.push({x, y - 1, level + 1});\n        }\n        maxMinutes = max(level, maxMinutes);\n    }\n    for (int i = 0; i < m; ++i) {\n        for (int j = 0; j < n; ++j) {\n            if (grid[i][j] == 1) return -1;\n        }\n    }\n    return maxMinutes;\n}\n<\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n        <pre><code class=\"language-c\">\nint orangesRotting(int** grid, int gridSize, int* gridColSize) {\n    int m = gridSize;\n    int n = gridColSize[0];\n    int queue[m * n][3];\n    int front = 0, rear = 0;\n    for (int i = 0; i < m; ++i) {\n        for (int j = 0; j < n; ++j) {\n            if (grid[i][j] == 2) {\n                queue[rear][0] = i;\n                queue[rear][1] = j;\n                queue[rear][2] = 0;\n                rear++;\n            }\n        }\n    }\n    int maxMinutes = 0;\n    while (front < rear) {\n        int x = queue[front][0];\n        int y = queue[front][1];\n        int level = queue[front][2];\n        front++;\n\n        if (x > 0 && grid[x - 1][y] == 1) {\n            grid[x - 1][y] = 2;\n            queue[rear][0] = x - 1;\n            queue[rear][1] = y;\n            queue[rear][2] = level + 1;\n            rear++;\n        }\n        if (x < m - 1 &#038;&#038; grid[x + 1][y] == 1) {\n            grid[x + 1][y] = 2;\n            queue[rear][0] = x + 1;\n            queue[rear][1] = y;\n            queue[rear][2] = level + 1;\n            rear++;\n        }\n        if (y < n - 1 &#038;&#038; grid[x][y + 1] == 1) {\n            grid[x][y + 1] = 2;\n            queue[rear][0] = x;\n            queue[rear][1] = y + 1;\n            queue[rear][2] = level + 1;\n            rear++;\n        }\n        if (y > 0 && grid[x][y - 1] == 1) {\n            grid[x][y - 1] = 2;\n            queue[rear][0] = x;\n            queue[rear][1] = y - 1;\n            queue[rear][2] = level + 1;\n            rear++;\n        }\n\n        if (level > maxMinutes) maxMinutes = level;\n    }\n    for (int i = 0; i < m; ++i) {\n        for (int j = 0; j < n; ++j) {\n            if (grid[i][j] == 1) return -1;\n        }\n    }\n    return maxMinutes;\n}\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n        <pre><code class=\"language-csharp\">\npublic int OrangesRotting(int[][] grid) {\n    int m = grid.Length;\n    int n = grid[0].Length;\n    Queue<(int, int, int)> queue = new();\n    for (int i = 0; i < m; i++) {\n        for (int j = 0; j < n; j++) {\n            if (grid[i][j] == 2) {\n                queue.Enqueue((i, j, 0));\n            }\n        }\n    }\n    int maxMinutes = 0;\n    while (queue.Count > 0) {\n        var (x, y, level) = queue.Dequeue();\n        if (x > 0 && grid[x - 1][y] == 1) {\n            grid[x - 1][y] = 2;\n            queue.Enqueue((x - 1, y, level + 1));\n        }\n        if (x < m - 1 &#038;&#038; grid[x + 1][y] == 1) {\n            grid[x + 1][y] = 2;\n            queue.Enqueue((x + 1, y, level + 1));\n        }\n        if (y < n - 1 &#038;&#038; grid[x][y + 1] == 1) {\n            grid[x][y + 1] = 2;\n            queue.Enqueue((x, y + 1, level + 1));\n        }\n        if (y > 0 && grid[x][y - 1] == 1) {\n            grid[x][y - 1] = 2;\n            queue.Enqueue((x, y - 1, level + 1));\n        }\n        maxMinutes = Math.Max(level, maxMinutes);\n    }\n    for (int i = 0; i < m; i++) {\n        for (int j = 0; j < n; j++) {\n            if (grid[i][j] == 1) return -1;\n        }\n    }\n    return maxMinutes;\n}\n  <\/code><\/pre>\n    <\/div>\n<\/div>\n<\/div>\n<script>\n    document.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                buttons.forEach((btn) => btn.classList.remove(\"active\"));\n                contents.forEach((content) =>\n                    content.classList.remove(\"active\")\n                );\n                button.classList.add(\"active\");\n                document\n                    .querySelector(\n                        `.wp_blog_code-tab-content[data-lang=\"${lang}\"]`\n                    )\n                    .classList.add(\"active\");\n            });\n        });\n    });\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Problem Statement: You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of<\/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":[322,260,176,175,211,811,810,174,172,173],"tags":[],"class_list":["post-7783","post","type-post","status-publish","format-standard","category-algorithms-and-data-structures","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/7783","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=7783"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/7783\/revisions"}],"predecessor-version":[{"id":7785,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/7783\/revisions\/7785"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=7783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=7783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=7783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}