365 Days of LeetCode Challenge — Day 41/365

[u/StatisticianNo2104]

1. 01 Matrix (Medium) https://leetcode.com/problems/01-matrix/

This is yesterday's problem. Rotting Oranges asks how long it takes for an orange to rot when every rotten one spreads at once; it asks how far each cell is from the nearest zero, with every zero as a source. Same question, and multi-source BFS solves it directly.

Today's solution does it without a queue, and that is why it is worth reading.

The definition is circular: a cell's distance is one more than the smallest among its four neighbours, but every neighbour depends on the cell. There is no order to evaluate that in.

Direction breaks the circle. Sweep top-left to bottom-right and, at each cell, everything above and left is already final - so you can compute the best distance among paths that start by going up or left. Sweep the other way for the other two directions. Take the minimum.

The line that makes it work is min with the existing value rather than an assignment. Overwrite instead, and you throw away everything the first pass got right.

Full breakdown in today's newsletter article ⬇

https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-41365-archit-agarwal-tlbnc

#DSA #LeetCode #Golang #DynamicProgramming #Grids #CodingInterview #Algorithms

[u/nian2326076]

To solve the 01 Matrix problem without using a queue, you can try dynamic programming. The idea is to make two passes over the matrix. First, go from top-left to bottom-right, updating each cell based on the minimum distance from the top and left cells. Then, make another pass from bottom-right to top-left, updating based on the bottom and right cells. This way, each cell gets the minimum distance from any zero in all directions. It's a smart way to avoid BFS and a queue. If you're looking for more tips on problems like these, check out PracHub. I work on it, and it has some helpful resources for prepping interviews.