Surrounded Regions-Leetcode 130

Problem Statement: Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Happy Case from Leetcode

Solution:

After going through the problem statement, it is very clear to us that we would be using some sort of Graph traversal Techniques i.e DFS or BFS.

Now, it depends on us to decide which technique to use and how.

Using DFS or BFS, there can be 100s of different solutions but we will focus on the optimized and efficient solution.

Question to ask yourself here are:

1. How do we use DFS efficiently?
2. Should we start DFS the moment we see an “O” and mark the entire region with “X”? If yes, then how should we realize that we should not mark the region with “X” if any one of the cells on the board belongs to the same region and is one of the corner cells.
3. Can we use DFS better? what if we scan all the corner rows and cells and the moment we see an “O” we start DFS and mark that region with any other character?

After asking these questions to yourself, I am sure you should be getting an idea of solving this problem. By now, you should have understood that asking 3rd question is the way to go as the problem particularly states we should not mark the entire region with “X” if any one of the cells of the region belongs to corner rows or columns.

Let us discuss the solution stepwise:

Step 1: Scan the first row using a loop and check if any of the cells has “O” in it, the moment you see an “O”, do the DFS and mark all the cells of that region with the character “Y”.

Step 2: Follow Step 1 for the last row, first column, and last column as well, because all these contain corner cells.

Step 3: Now that we have scanned all possible corner cells and marked the entire region having corner cells with the character “Y”. You will see that the regions with characters “O” and which do not have any corner cells are isolated.

Step 4: Go through the board again, mark all the cells with the character “O” as “X”. And mark all the cells with characters “Y” as “X”.

Time Complexity: O(N²) as in worse case we are only traversing all the cells of the board.

Space Complexity: O(N²) due to Recursive stack space and the worst case can happen if all the cells in the board are marked as “O”.

Below is the code Snippet:

Hit clap if you liked it! This motivates me a lot.