{"id":3610,"date":"2021-11-11T18:17:18","date_gmt":"2021-11-11T12:47:18","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3610"},"modified":"2021-11-11T18:17:19","modified_gmt":"2021-11-11T12:47:19","slug":"rotten-oranges-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/rotten-oranges-problem\/","title":{"rendered":"Rotten Oranges Problem With Solution"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#sample-test-cases\">Sample Test Cases<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#optimal-approach\">Optimal Approach:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an <strong>n * m<\/strong> grid, where each element can contain one of the 3 given values,&nbsp;<\/p>\n\n\n\n<ul><li><strong>0<\/strong> represents an <strong>empty cell<\/strong>.<\/li><li><strong>1<\/strong> represents a cell containing <strong>fresh orange<\/strong>.<\/li><li><strong>2<\/strong> represents a cell containing <strong>rotten orange<\/strong>.<\/li><\/ul>\n\n\n\n<p>Every day, any fresh orange that is <strong>4-directionally adjacent<\/strong> to a rotten orange becomes rotten.<\/p>\n\n\n\n<p>Return the <strong>minimum number of days<\/strong> that must elapse until no cell has a fresh orange. If this is <strong>impossible<\/strong>, return -1.<\/p>\n\n\n\n<h2 id=\"sample-test-cases\">Sample Test Cases<\/h2>\n\n\n\n<p>Input 1:<\/p>\n\n\n\n<p>grid = [[2, 1, 0],&nbsp;<\/p>\n\n\n\n[1, 1, 0],&nbsp;<\/p>\n\n\n\n[0, 1, 1]]\n\n\n\n<p>Output 1:<\/p>\n\n\n\n<p>4<\/p>\n\n\n\n<p>Explanation 1:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"220\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"rotting oranges example\"  class=\"wp-image-3677 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-1024x220.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-1024x220.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-300x65.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-768x165.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-1536x330.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-2048x440.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-380x82.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-550x118.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-800x172.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example-1160x249.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/rotting-oranges-example.png 2665w\" ><\/figure>\n\n\n\n<p>From the figure, we see that on the 4th day, all the oranges get rotten.<\/p>\n\n\n\n<p>Input 2:<\/p>\n\n\n\n<p>grid = [[2, 1, 0],&nbsp;<\/p>\n\n\n\n[1, 1, 0],&nbsp;<\/p>\n\n\n\n[1, 0, 1]]\n\n\n\n<p>Output 2:<\/p>\n\n\n\n<p>-1<\/p>\n\n\n\n<p>Explanation 2:<\/p>\n\n\n\n<p>The orange at (2, 0) will never get rotten.&nbsp;<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach:<\/h2>\n\n\n\n<p>In the naive approach, we can traverse through all the oranges in the grid in multiple rounds.<\/p>\n\n\n\n<p>In each round, we can rot the oranges to adjacent positions of oranges that had gotten rotten in the previous round. The algorithm is as follows:<\/p>\n\n\n\n<ul><li>Create variables <strong>days <\/strong>and <strong>flag <\/strong>and initialize them to 2 and false respectively.<\/li><li>We run an infinite loop that will continue until there is no cell in the grid, which is changed in the current iteration.<\/li><li>Traverse through every element of the grid and if the elements of the matrix are equal to <strong>days<\/strong> and its adjacent elements values are 1, then update them to <strong>days + 1.<\/strong> Also, set the <strong>flag<\/strong> to true.<\/li><li>Search for a cell containing value 1, by traversing the matrix. If found return -1.<\/li><li>Else return days &#8211; 2.<\/li><\/ul>\n\n\n\n<p><strong>Code \/ Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool isSafe(vector &lt; vector &lt; int >> &amp; grid, int i, int j) {\n  int n = grid.size();\n  int m = grid[0].size();\n  return (i >= 0 &amp;&amp; j >= 0 &amp;&amp; i &lt; n &amp;&amp; j &lt; m);\n}\nint numberOfDays(vector &lt; vector &lt; int >> &amp; grid) {\n  int days = 2;\n  bool flag = false;\n  int n = grid.size();\n  int m = grid[0].size();\n  while (1) {\n    for (int i = 0; i &lt; n; i++) {\n      for (int j = 0; j &lt; m; j++) {\n        if (grid[i][j] == days) {\n          if (isSafe(grid, i + 1, j) &amp;&amp; grid[i + 1][j] == 1) {\n            grid[i + 1][j] = grid[i][j] + 1;\n            flag = true;\n          }\n          if (isSafe(grid, i, j + 1) &amp;&amp; grid[i][j + 1] == 1) {\n            grid[i][j + 1] = grid[i][j] + 1;\n            flag = true;\n          }\n          if (isSafe(grid, i - 1, j) &amp;&amp; grid[i - 1][j] == 1) {\n            grid[i - 1][j] = grid[i][j] + 1;\n            flag = true;\n          }\n          if (isSafe(grid, i, j - 1) &amp;&amp; grid[i][j - 1] == 1) {\n            grid[i][j - 1] = grid[i][j] + 1;\n            flag = true;\n          }\n        }\n      }\n    }\n    if (flag == false) {\n      break;\n    }\n    flag = false;\n    days++;\n  }\n  for (int i = 0; i &lt; n; i++) {\n    for (int j = 0; j &lt; m; j++) {\n      if (grid[i][j] == 1) {\n        days = -1;\n      }\n    }\n  }\n  return days == -1 ? days : days - 2;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static boolean isSafe(int[][] grid, int i, int j) {\n  int n = grid.length;\n  int m = grid[0].length;\n  return (i >= 0 &amp;&amp; j >= 0 &amp;&amp; i &lt; n &amp;&amp; j &lt; m);\n}\npublic static int numberOfDays(int[][] grid) {\n  int days = 2;\n  boolean flag = false;\n  int n = grid.length;\n  int m = grid[0].length;\n  while (true) {\n    for (int i = 0; i &lt; n; i++) {\n      for (int j = 0; j &lt; m; j++) {\n        if (grid[i][j] == days) {\n          if (isSafe(grid, i + 1, j) &amp;&amp; grid[i + 1][j] == 1) {\n            grid[i + 1][j] = grid[i][j] + 1;\n            flag = true;\n          }\n          if (isSafe(grid, i, j + 1) &amp;&amp; grid[i][j + 1] == 1) {\n            grid[i][j + 1] = grid[i][j] + 1;\n            flag = true;\n          }\n          if (isSafe(grid, i - 1, j) &amp;&amp; grid[i - 1][j] == 1) {\n            grid[i - 1][j] = grid[i][j] + 1;\n            flag = true;\n          }\n          if (isSafe(grid, i, j - 1) &amp;&amp; grid[i][j - 1] == 1) {\n            grid[i][j - 1] = grid[i][j] + 1;\n            flag = true;\n          }\n        }\n      }\n    }\n    if (flag == false) {\n      break;\n    }\n    flag = false;\n    days++;\n  }\n  for (int i = 0; i &lt; n; i++) {\n    for (int j = 0; j &lt; m; j++) {\n      if (grid[i][j] == 1) {\n        days = -1;\n      }\n    }\n  }\n  return days == -1 ? days : days - 2;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def isSafe(grid, i, j):\n    n = len(grid)\n    m = len(grid[0])\n    return i >= 0 and j >= 0 and i &lt; n and j &lt; m\n\n\ndef numberOfDays(grid):\n    days = 2\n    flag = False\n    n = len(grid)\n    m = len(grid[0])\n    while 1:\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == days:\n                    if isSafe(grid, i + 1, j) and grid[i + 1][j] == 1:\n                        grid[i + 1][j] = grid[i][j] + 1\n                        flag = True\n                    if isSafe(grid, i - 1, j) and grid[i - 1][j] == 1:\n                        grid[i - 1][j] = grid[i][j] + 1\n                        flag = True\n                    if isSafe(grid, i, j + 1) and grid[i][j + 1] == 1:\n                        grid[i][j + 1] = grid[i][j] + 1\n                        flag = True\n                    if isSafe(grid, i, j - 1) and grid[i][j - 1] == 1:\n                        grid[i][j - 1] = grid[i][j] + 1\n                        flag = True\n        if flag == False:\n            break\n        flag = False\n        days += 1\n    for i in range(n):\n        for j in range(m):\n   if grid[i][j] == 1:\n                days = -1\n    return -1 if days == -1 else days - 2<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O((n * m) * (n * m))<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"optimal-approach\">Optimal Approach:<\/h2>\n\n\n\n<p>We can solve this problem optimally using the <strong>\u201cMultisource BFS\u201d<\/strong> algorithm on a grid. The key observation is that fresh oranges adjacent to rotten oranges are rotten on day 1, those adjacent to those oranges are rotten on day 2, and so on. The phenomenon is similar to a <strong>level order traversal<\/strong> on a graph, where all the initial rotten oranges act as root nodes.<\/p>\n\n\n\n<p>We can just push all these root nodes into a queue and perform <strong>BFS on a grid<\/strong> algorithm, to calculate the total time taken to rot all the oranges. If all oranges are not rotten before our algorithm terminates, we will return <strong>-1<\/strong>.<\/p>\n\n\n\n<p>The algorithm is described as follows:<\/p>\n\n\n\n<ul><li>Initialize the number of <strong>days <\/strong>to 0.<\/li><li>Declare a <strong>queue<\/strong> of appropriate datatype and push all the cells containing <strong>rotten oranges<\/strong> into it one by one.<\/li><li>While the queue is not empty, pop the cell from the front of the queue, and try to go all its neighbors in 4 directions, keeping check that they lie within the boundary of the matrix, and changing their values to <strong>2(rotten orange)<\/strong>. Push all these adjacent into the queue, and continue the algorithm until the next iteration.<\/li><li>Keep updating the <strong>days <\/strong>passed variable appropriately, and continue the algorithm till all the cells are visited.<\/li><li>Iterate through the grid again and if a cell with a fresh orange is found, return <strong>-1.<\/strong><\/li><li>Else return the <strong>days <\/strong>passed.<\/li><\/ul>\n\n\n\n<p><strong>Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">const int dx[] = { 1, 0, -1, 0};\nconst int dy[] = {0, 1, 0, -1};\nbool isSafe(vector &lt; vector &lt; int >> &amp; grid, int x, int y) {\n  int r = grid.size();\n  int c = grid[0].size();\n  return (x >= 0 &amp;&amp; x &lt; r &amp;&amp; y >= 0 &amp;&amp; y &lt; c &amp;&amp; grid[x][y] == 1);\n}\nint numberOfDays(vector &lt; vector &lt; int >> &amp; grid) {\n  int r = grid.size();\n  int c = grid[0].size();\n  queue &lt; pair &lt; int, int >> q;\n  for (int i = 0; i &lt; r; i++) {\n    for (int j = 0; j &lt; c; j++) {\n      if (grid[i][j] == 2) {\n        q.push({ i,  j });\n      }\n    }\n  }\n  int days = -2;\n  while (!q.empty()) {\n    int qs = q.size();\n    while (qs--) {\n      pair &lt; int, int > p = q.front();\n      int x = p.first;\n      int y = p.second;\n      q.pop();\n      for (int i = 0; i &lt; 4; i++) {\n        if (isSafe(grid, x + dx[i], y + dy[i])) {\n          q.push({\n            x + dx[i],\n            y + dy[i]\n          });\n          grid[x + dx[i]][y + dy[i]] = 2;\n        }\n      }\n    }\n    days += 1;\n  }\n  for (int i = 0; i &lt; r; i++) {\n    for (int j = 0; j &lt; c; j++) {\n      if (grid[i][j] == 1) {\n        return -1;\n      }\n    }\n  }\n  return days == -2 ? 0 : days + 1;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int dx[] = {1, 0, -1, 0};\nstatic int dy[] = {0, 1, 0, -1};\npublic static int numberOfDays(int[][] grid) {\n  int r = grid.length;\n  int c = grid[0].length;\n  int days = 0, countOfOnes = 0;\n  Queue &lt; int[] > q = new LinkedList &lt; > ();\n  for (int i = 0; i &lt; r; i++) {\n    for (int j = 0; j &lt; c; j++) {\n      if (grid[i][j] == 2) {\n        q.add(new int[] {i, j});\n      }\n      if (grid[i][j] == 1) {\n        countOfOnes += 1;\n      }\n    }\n  }\n  if (countOfOnes == 0) {\n    return 0;\n  }\n  while (!q.isEmpty()) {\n    int size = q.size();\n    while (size--> 0) {\n      int[] temp = q.remove();\n      int i = temp[0], j = temp[1];\n      for (int l = 0; l &lt; 4; l++) {\n        int nr = i + dx[l], nc = j + dy[l];\n        if (nr &lt; 0 || nc &lt; 0 || nr == r || nc == c) {\n          continue;\n        }\n        if (grid[nr][nc] == 1) {\n          countOfOnes -= 1;\n          q.add(new int[] {\n            nr,\nnc\n          });\n          grid[nr][nc] = 2;\n        }\n      }\n    }\n    if (q.size() > 0) {\n      days += 1;\n    }\n  }\n  return countOfOnes == 0 ? days : -1;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def numberOfDays(grid):\n    r = len(grid)\n    c = len(grid[0])\n    fresh = 0\n    queue = []\n    vis = set()\n    for i in range(r):\n        for j in range(c):\n            if grid[i][j] == 2:\n                queue.append((i, j, 0))\n                vis.add((i, j))\n            elif grid[i][j] == 1:\n                fresh += 1\n    if not fresh:\n        return 0\n    while queue:\n        size = len(queue)\n\n        while size:\n            x, y, days = queue.pop(0)\n            if x &lt; r - 1 and (x + 1, y) not in vis and grid[x + 1][y] == 1:\n                queue.append((x + 1, y, days + 1))\n                vis.add((x + 1, y))\n                fresh -= 1\n            if x > 0 and (x - 1, y) not in vis and grid[x - 1][y] == 1:\n                queue.append((x - 1, y, days + 1))\n                vis.add((x - 1, y))\n                fresh -= 1\n            if y &lt; c - 1 and (x, y + 1) not in vis and grid[x][y + 1] == 1:\n  queue.append((x, y + 1, days + 1))\n                vis.add((x, y + 1))\n                fresh -= 1\n            if y > 0 and (x, y - 1) not in vis and grid[x][y - 1] == 1:\n                queue.append((x, y - 1, days + 1))\n                vis.add((x, y - 1))\n                fresh -= 1\n            size -= 1\n    return -1 if fresh else days<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n * m)<\/li><li>Space Complexity: O(n * m)<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>1. What is the main insight which can be learned from this problem?<\/strong><\/p>\n\n\n\n<p>A.&nbsp; The key insight to learn from this problem is to learn how to model a seemingly unrelated problem into a graph traversal problem.<\/p>\n\n\n\n<p><strong>2. What is the difference between Single Source and Multi-Source BFS?<\/strong><\/p>\n\n\n\n<p>A. The difference is as the name suggests, in multi-source BFS, multiple nodes act as the root node of the graph network simultaneously.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an n * m grid, where each element can contain one of the 3 given&hellip;\n","protected":false},"author":5,"featured_media":3676,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[561],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3610"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3610"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3610\/revisions"}],"predecessor-version":[{"id":3679,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3610\/revisions\/3679"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3676"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3610"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3610"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3610"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}