tag:blogger.com,1999:blog-4731036105252322780.post6047657740335439550..comments2024-03-01T02:55:58.951-08:00Comments on Buttercola: Leetcode: Walls and GatesButter is looking for a jobhttp://www.blogger.com/profile/01481083468821703855noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-4731036105252322780.post-33592600886614231862020-09-19T16:00:57.050-07:002020-09-19T16:00:57.050-07:00Yes that does and will take less time as well! and...Yes that does and will take less time as well! and such similar question is there on Leetcode as well!Anonymoushttps://www.blogger.com/profile/12749158547775476469noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-23980875062770258192020-06-18T20:59:45.714-07:002020-06-18T20:59:45.714-07:00I dont think the visited 2D array is required in t...I dont think the visited 2D array is required in the case of DFS, because we are increasing the distance from 0 and and the below if condition will always be true when we visit an already visited cell hence accomplishing the purpose of the visited 2D array. <br />if (distance > rooms[row][col]) {<br /> return;<br /> }<br /><br />Let me know your thoughtsAnonymoushttps://www.blogger.com/profile/08662386776295723251noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-59255031436956274152020-02-17T07:40:57.984-08:002020-02-17T07:40:57.984-08:00Yes
Yes<br />Anonymoushttps://www.blogger.com/profile/07207399335565104931noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-30998355307940975942019-12-20T14:51:35.484-08:002019-12-20T14:51:35.484-08:00This is typical BFS problem. Add all the gates fir...This is typical BFS problem. Add all the gates first in queue and start from there.<br />DFS should not work here. BFS is guaranteed to provide minimum distance here as its an unweighted graph, so distance is equal to number of edges traveled.amanhttps://www.blogger.com/profile/08257755136886448862noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-22694807472388724552019-06-20T21:04:10.837-07:002019-06-20T21:04:10.837-07:00Hi,In case of DFS approach, would the time complex...Hi,In case of DFS approach, would the time complexity still be O(V+E)?<br />Unlike the standard DFS where each cell would be visited only once,here we may visit a cell multiple times cause we mark a cell unvisited after finding a path to it.<br />Can you please clarify this.doer8609https://www.blogger.com/profile/04101958443240719598noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-9919079488063625002016-01-12T22:03:59.955-08:002016-01-12T22:03:59.955-08:00What do you mean by putting all gate cells into be...What do you mean by putting all gate cells into beginning queue? The queue here is used to store the updated room point. Also, in order to get all the gates, you need at least to visit all the point in matrix rooms. This is exactly what has been done in the wallsAndGates(). So I think the BFS here is correct at this point.Anonymoushttps://www.blogger.com/profile/01881283152953540590noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-17744544614415150272015-10-19T16:32:24.136-07:002015-10-19T16:32:24.136-07:00why not put all gate cells into the queue at the b...why not put all gate cells into the queue at the beginning and then BFS the matrix. it is simpler in logic and guarantees O(m*n) complexityAnonymoushttps://www.blogger.com/profile/14452744908400837816noreply@blogger.com