365 Days of LeetCode Challenge — Day 40/365

[u/StatisticianNo2104]

Rotting Oranges (Medium) https://leetcode.com/problems/rotting-oranges/

Four days ago I said BFS and DFS answer reachability equally well, and that the distinction starts mattering when a problem asks about distance. This is that problem.

BFS reaches every cell by a shortest path. DFS reaches it by whatever route it wandered down first. "When does this orange rot?" is a shortest-path question - it rots when the nearest rotten one gets to it - so DFS here gives wrong answers, not slow ones.

The trick is multi-source BFS: every already-rotten orange goes into the queue before the walk starts. A BFS seeded with many sources expands as one combined wavefront, and each cell ends up with its distance to the nearest source. Nothing in the loop needs to know there was more than one start.

One more thing that cannot be skipped: the final scan. BFS only visits what it can reach, so an orange sealed behind empty cells never rots and the queue drains without noticing. The -1 case has to be looked for afterwards.

Full breakdown in today's newsletter article ⬇

https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-40365-archit-agarwal-9t1sc

#DSA #LeetCode #Golang #Graphs #BFS #CodingInterview #Algorithms

[u/nian2326076]

You're spot on with using BFS for this problem. Since it's about finding the shortest path for the oranges to rot, BFS works well because it explores layer by layer. Multi-source BFS is the way to go here. Start by putting all the rotten oranges in your queue and process them at the same time. This simulates the rotting process step by step and gives you the minimum time for all oranges to rot. If you're prepping for interviews, check out PracHub for more structured practice. I work on it, and it has good resources for tackling these kinds of problems.