Skip to content

Rotting Oranges

Leetcode 994. Rotting Oranges

Leetcode 994. Rotting Oranges

Problem

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 minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 01, or 2.

Source: Leetcode 994. Rotting Oranges

Solution

This problem can be solved using Breadth First Search (BFS) algorithm, which is an algorithm originally invented to “for searching a tree data structure for a node that satisfies a given property. (BFS – wikipedia)

BFS and its application in finding connected components of graphs were invented in 1945 by Konrad Zuse, in his (rejected) Ph.D. thesis on the Plankalkül programming language, but this was not published until 1972.[ It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961).

Source: BFS – wikipedia
How BFS Works

Let’s say we have a graph data structure where nodes are connected by edges. We also have a queue to store node values. We want to find the distance from a start node to an end node. Here, each node has same amount of distance, say 1 unit, from its adjacent node.

BFS takes the start node and pushes into the queue and assigns current_distance = 0. This is the distance from the current node (which is just pushed into the queue) from itself. This is the first step.

Then it runs a loop until the queue is empty or it reaches to the end node. Inside that loop, it pops node from the queue, then take adjacent elements of that (recently popped) node into the queue and update distance of adjacent nodes as current_distance + 1. This loop runs until the queue is empty or the algorithm finds the end node.

As we can visualize, BFS works like a wave or a layered approach. For a single node, it explores all nodes adjacent to it. Before explore all adjacent nodes, it doesn’t go in any depth.

However, let’s see this algorithm in action to solve this problem. It’s better to understand visually!

BFS in Rotting Oranges

Let’s say we have a grid as below. We have some cells with 0 value having no oranges, with 2 value having rotting oranges and 1 value having good oranges.

We will have to find how many minutes will elapse until all oranges are rotted, right?

In other words, we need to find how many layers are away from a rotting orange to cover all the good oranges!

For example, the first rotting orange is 2 with layer 0 and coordinate {0, 0}. In the next layer, we have 1 with layer 1 and coordinate {0, 1}. Then we have 1 with layer 2 and coordinate {1, 1} and so on.

See we are just exploring the adjacent nodes of a node and assigning layer + 1 to the newly explored node, right?

Let’s get back to the solution again.

We have a queue which will store a data structure structure for a node like { node_coordinate_x, node_coordinate_y, distance}.

At first we count how many fresh oranges (i.e. nodes with 1) we have and save it in a variable like total_fresh = 6.

Then we find all the rotting oranges push them in our queue. Remember, while pushing we are adding their coordinates (in this case, i and j values) and their initial distance (in other words, layer number). For the first rotting orange, it is {0, 0, 0}.

Now we will loop through the queue, pop the first node from queue and explore each adjacent 1 nodes (of the popped node) one after another. There are two adjacent nodes which are {1, 0} and {0, 1}. Since {1, 0} do not have any fresh orange, we will not take that node.

So, there is only one adjacent 1 node (i.e. node with fresh orange) of node {0, 0} which is node {0, 1}.

We push the explored node to the queue and update its distance to be 1 (distance = distance of popped node + 1).

Since we explored a fresh node (i.e. node with value 1) and made it rotten, our total_fresh is now reduced to 1!

Now we will explore the adjacent nodes of node {0, 1}. In the same way, we find node {1, 1} should be added in the queue. We update distance of this node and update total_fresh as below image.

Now we will explore the adjacent nodes of node {1, 1}. In the same way, we find node {1, 2} and {2,1} should be added in the queue. Here, do we need to maintain any order when we find more than one valid adjacent node? No, not necessary at least for this problem.

We update distances of these new nodes and update total_fresh as below image. Since we found two fresh oranges in these nodes, we reduced total_fresh by 2.

We now will explore the adjacent nodes of node {1, 2} (it could be node {2, 1} also, order doesn’t matter). In the same way, we find node {2, 2} should be added in the queue. We update distance of this node and update total_fresh as below image.

Then we will explore the adjacent nodes of node {2, 1}. But wait, there was only one valid adjacent node which is {2, 2}. But that one is already explored! So, we won’t do anything with it and continue to the loop.

Now we will explore the adjacent nodes of node {2, 2}. We find node {2, 3} should be added in the queue. We update distance of this node and update total_fresh as below image.

We see, total_fresh has become 0 when we reached at node {2, 3}. So, the distance when we reached node {2, 3} should be the time required to make all oranges rotten! So, we simply return this answer :).

Code
C++
class Solution {
public:
    int countFresh(vector<vector<int>>& grid){
        int total_fresh = 0;
        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[i].size(); j++)
                if(grid[i][j] == 1) total_fresh+= 1;
        return total_fresh;
    }
    
    int orangesRotting(vector<vector<int>>& grid) {
        int total_fresh = countFresh(grid);
        if(total_fresh == 0)
            return 0;
        
        queue<vector<int>> q;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 2) {
                    q.push({i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        
        vector<vector<int>> dir = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        
        while(!q.empty()){
            
            vector<int> parent = q.front(); q.pop();
            int r = parent[0];
            int c = parent[1];
            int dist = parent[2];
            
            for(int i = 0; i < 4; i++){
                int new_r = r + dir[i][0];
                int new_c = c + dir[i][1];
                
                if(0 <= new_r && new_r < grid.size() && 0 <= new_c && new_c < grid[0].size()){
                    if(grid[new_r][new_c] == 1 && !visited[new_r][new_c]){
                        visited[new_r][new_c] = true;
                        q.push({new_r, new_c, dist + 1});
                        total_fresh -= 1;
                        if(total_fresh == 0) return dist + 1;
                    }
                }
            }
        }
        
        return -1;
    }
};
Complexity Analysis

Since we have to explore all the nodes, in worst case, the time and space complexity will be the total number of cells in the matrix.

Conclusion

Hope you enjoyed the solution, though it was an easy problem and a simple version of BFS algorithm. 🙂 

Did we make it too complex explaining this? 🙁 Not sure!

Can you write down about it?

Also, you can let us know what difficulty you are facing solving leetcode problems in general. If you love our blog or hate it, please shout out!

Happy coding! 🙂

111 thoughts on “Rotting Oranges”

  1. Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.

  2. ebenin amını gör dolandırıcı piç

    destek talebi açıyorum cevap vermiyorsun beni bu işlere bulaştırma paramı geri iade et destek taleplerine bak dolandırıcı

  3. Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.

  4. Hi there! This post could not be written much better!
    Looking at this article reminds me of my previous roommate!

    He continually kept talking about this. I most certainly will forward this post to him.

    Pretty sure he’ll have a great read. Many thanks
    for sharing!

  5. An impressive share, I just given this onto a colleague who was doing a little analysis on this. And he in fact bought me breakfast because I found it for him.. smile. So let me reword that: Thnx for the treat! But yeah Thnkx for spending the time to discuss this, I feel strongly about it and love reading more on this topic. If possible, as you become expertise, would you mind updating your blog with more details? It is highly helpful for me. Big thumb up for this blog post!

  6. Today, I went to the beach with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!

  7. Эффективное теплосбережение облицовки — счастье и экономия в жилом здании!
    Согласитесь, ваш коттедж заслуживает наилучшего! Изоляция внешних стен – не голос решение для сбережения на тепле, это вложение в комфорт и долговечность вашего помещения.
    ✨ Почему изоляция с нами-специалистами?
    Квалификация: Наша команда – профессиональные. Наш коллектив заботимся о каждом аспекте, чтобы обеспечить вашему дому идеальное теплосбережение.
    Цена утепления: Мы ценим ваш средства. [url=https://stroystandart-kirov.ru/]Утепление фасадов цена за м2[/url] – начиная с 1350 руб./кв.м. Это вложение средств в ваше комфортное будущее!
    Энергосбережение: Забудьте о потерях тепловой энергии! Материалы, которые мы используем не только сохраняют тепловое уюта, но и дарят вашему коттеджу новый уровень энергоэффективности.
    Создайте свой домашнюю обстановку комфортным и стильным и модным!
    Подробнее на [url=https://stroystandart-kirov.ru/]www.n-dom.ru
    [/url]
    Не покидайте свой коттедж на произвол судьбы. Доверьтесь нашей бригаде и создайте тепло вместе с нами-профессионалами!

  8. Fascinating blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple tweeks would really make my blog stand out. Please let me know where you got your design. With thanks

  9. Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your webpage? My blog site is in the very same area of interest as yours and my users would certainly benefit from a lot of the information you provide here. Please let me know if this alright with you. Appreciate it!

  10. Эффективное теплосбережение облицовки — комфорт и экономическая выгода в домашнем коттедже!
    Согласитесь, ваш жилище заслуживает выдающегося! Теплоизоляция облицовки – не единственно решение для сбережения на отоплении, это вложение денег в удобство и устойчивость вашего недвижимости.
    ✨ Почему термоизоляция с нашей компанией?
    Профессионализм: Наша – опытные. Наш коллектив заботимся о каждой, чтобы обеспечить вашему жилью идеальное утепление.
    Стоимость услуги теплоизоляции: Наша компания ценим ваш средства. [url=https://stroystandart-kirov.ru/]Услуги по утеплению стен снаружи стоимость работ[/url] – начиная от 1350 руб./кв.м. Это инвестиция в ваше уютное будущее!
    Энергоэффективность: Забудьте о термопотерях! Наши не только сохраняют тепловое уюта, но и дарят вашему жилищу новый уровень комфорта энергоэффективности.
    Обустройте свой домашнюю обстановку комфортным и стильным!
    Подробнее на [url=https://stroystandart-kirov.ru/]http://stroystandart-kirov.ru[/url]
    Не покидайте свой загородный дом на произвольное решение. Доверьтесь мастерам и создайте комфорт вместе с нашей командой!

  11. Geliştiriciler için ayrıntılı API Hizmeti sunuyoruz! Tüm hizmetlere ücretsiz API ile kolayca Çekim Yapabilirsiniz.

  12. Web siteleri ve mobil uygulamalar için geçerli SMS Onay alarak Hesap güvenliğinizi artırın. Birden fazla ülkeden numara alabilirsiniz.

  13. Ты очень хорошо подчеркнули важность этой темы.
    Предлагаю воспользоваться журналистского расследования для объективного выяснения всех аспектов этой ситуации!

  14. Наша группа искусных исполнителей предоставлена подать вам прогрессивные технологии, которые не только обеспечивают прочную протекцию от холода, но и подарят вашему коттеджу современный вид.
    Мы занимаемся с современными строительными материалами, обеспечивая долгий срок работы и великолепные результирующие показатели. Теплоизоляция фасада – это не только экономия на тепле, но и заботливость о окружающей среде. Энергоэффективные технические средства, какие мы используем, способствуют не только вашему, но и сохранению природы.
    Самое центральное: [url=https://ppu-prof.ru/]Стоимость утепления фасада[/url] у нас открывается всего от 1250 рублей за квадратный метр! Это доступное решение, которое превратит ваш домашний уголок в подлинный приятный локал с небольшими затратами.
    Наши проекты – это не только изолирование, это постройка помещения, в где любой элемент отражает ваш персональный образ действия. Мы примем во внимание все ваши пожелания, чтобы осуществить ваш дом еще еще более гостеприимным и привлекательным.
    Подробнее на [url=https://ppu-prof.ru/]веб-сайте[/url]
    Не откладывайте дела о своем корпусе на потом! Обращайтесь к экспертам, и мы сделаем ваш жилище не только теплее, но и стильным. Заинтересовались? Подробнее о наших трудах вы можете узнать на веб-ресурсе. Добро пожаловать в универсум удобства и качества.

  15. Thanks for another informative website. The place else may just I am getting that type of info written in such an ideal means? I’ve a undertaking that I am simply now running on, and I’ve been at the glance out for such information.

  16. Уважаемые Клиенты!
    Приводим вам оригинальное элемент в мире стилистики внутреннего пространства – шторы плиссе. Если вы движетесь к отличию в каждом аспекте вашего домашнего, то эти портьеры станут прекрасным паттерном для вас.
    Что делает шторы плиссе настолько единственными? Они объединяют в себе в себе шик, работоспособность и полезность. Благодаря индивидуальной формации, прогрессивным тканям, шторы плиссе идеально подходят к для всякого комнатки, будь то гостинка, спальная комната, плитки или секретарское поле.
    Закажите [url=https://tulpan-pmr.ru]плиссе на окна[/url] – воссоздайте уют и великолепие в вашем доме!
    Чем привлекательны шторы плиссе для вас? Во-первых, их самобытный макет, который прибавляет к привлекательность и вкус вашему жилищу. Вы можете подобрать из различных текстур, цветов и стилей, чтобы подчеркнуть самобытность вашего дома.
    Кроме того, шторы плиссе предлагают массивный ряд практических вариантов. Они могут контролировать степень света в месте, преграждать от солнечного света, поддерживать закрытость и формировать уютную атмосферу в вашем жилище.
    Наш сайт: [url=https://tulpan-pmr.ru]http://tulpan-pmr.ru[/url]
    Наша компания поможем вам подобрать шторы плиссе, какие замечательно соответствуют для вашего внутреннего пространства!

  17. For the past few days I’ve been an avid follower of this awesome site, they have brilliant content for fans. The site owner excels at captivating readers. I’m thrilled and hope they keep up their magnificent work.

  18. This resource is incredible. The wonderful data exhibits the manager’s earnestness. I’m stunned and expect more such mind blowing presents.

  19. Hello, Neat post. There’s an issue with your site in web explorer,
    would test this? IE still is the marketplace chief and a large portion of people will leave out your excellent
    writing because of this problem.

  20. But wanna input on few general things, The website design and style is perfect, the articles is really wonderful. “The sun sets without thy assistance.” by The Talmud.

  21. I have been absent for some time, but now I remember why I used to love this website. Thank you, I¦ll try and check back more frequently. How frequently you update your web site?

  22. Мы специалисты специалистов по SEO-оптимизации, специализирующихся на повышении посещаемости и рейтинга вашего сайта в поисковых системах.
    Наша команда постигли успехи в своей области и хотим поделиться с вами нашим опытом и навыками.
    Какие услуги мы предоставляем:
    • [url=https://seo-prodvizhenie-ulyanovsk1.ru/]сео продвижение сайтов цена москва[/url]
    • Комплексный анализ вашего сайта и разработка индивидуальной стратегии продвижения.
    • Оптимизация контента и технических характеристик вашего сайта для достижения наивысших результатов.
    • Ежемесячный мониторинг и анализ данных для постоянного совершенствования вашего онлайн-присутствия.
    Подробнее [url=https://seo-prodvizhenie-ulyanovsk1.ru/]https://seo-prodvizhenie-ulyanovsk1.ru/[/url]
    Многие наши клиенты отмечают улучшения: рост посещаемости, улучшение позиций в поисковых системах и, конечно, рост бизнеса. Мы готовы предоставить вам бесплатную консультацию, для обсуждения ваших потребностей и разработки стратегии продвижения, соответствующей вашим целям и бюджету.
    Не упустите возможность улучшить свои позиции в интернете. Свяжитесь с нами уже сегодня.

Leave a Reply

Your email address will not be published. Required fields are marked *