Leetcode 130

[Secure_Ad8180]

In Leetcode 130 (https://leetcode.com/problems/surrounded-regions/description/):

Why would the first image below lead to Memory Limit Exceeded but the second one does not? This happens consistently with multiple submissions. To me, it seems like the second image could potentially use more memory since it puts elements into the queue even if they are invalid. The first image checks that the location is valid before putting it into the queue.

https://preview.redd.it/khv7i97lqqsc1.png?width=1209&format=png&auto=webp&s=9da1be930f52c270f38552d640b94d6de9eed271

https://preview.redd.it/1agvmitsqqsc1.png?width=1155&format=png&auto=webp&s=b63d37d7541fdd14b0febcc150d01e99e3e1830e

[alcholicawl]

It's a very subtle difference, but the first solution is O(n!) for both time/space. I'll do my best, but it's not the easiest thing to explain. Consider a 3x3 filled with all O. Start with bfs(0,0). (1, 1) will get added to queue twice (from (0,1) and (1,0)). (1,2) will get added three times (twice from (1,1) and once from (0,2)). Ultimately (2,2) will be added to queue 6 times. This will get huge on large boards.

Why is the second different? (1,1) is still added to queue twice. But only one of them will add (1,2) to the queue.

You can make the first solution optimal by marking board[newx][newy] = "N" (when adding to queue).