Surrounded Regions - Leetcode Solution

Surrounded Regions problem on leetcode:

Given an m x n matrix board containing 'X' and 'O', flip all 'O's which are surrounded by 'X's to 'X'.

A region is considered to be surrounded by 'X's if all the cells in the region that are in the border of the matrix are 'X's.

Example: Input: board = [ ['X','X','X','X'], ['X','O','O','X'], ['X','X','O','X'], ['X','O','X','X'] ] Output: [ ['X','X','X','X'], ['X','X','X','X'], ['X','X','X','X'], ['X','O','X','X'] ] Explanation: Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' from the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Approach:

1. We will be using a DFS traversal to find all the 'O's which are not surrounded by 'X's.
2. First, we initialize the borders of the matrix and add them to the queue. We won't be changing any 'O' on the borders. If any 'O' is found on the borders, we can assume it is not surrounded by 'X's.
3. We traverse every cell in the matrix and if 'O' is found, we push it to the queue and mark it as 'visited' by changing it to 'N' (because it will now be surrounded by 'X's).
4. Now, we will run a DFS until the queue is empty. In the DFS function, for every 'O' present in the queue, we will mark it as 'visited' by changing it to 'N' (because it will now be surrounded by 'X's) and add its neighbouring cells to the queue.
5. After the DFS is completed, we iterate through the matrix again and change all 'O's to 'X's and all 'N's to 'O's.

Code:

class Solution { public: void solve(vector<vector<char>>& board) { int m = board.size(); if(m==0) return; int n = board[0].size(); queue<pair<int,int>> q; // Adding elements on the borders to the queue for(int i=0;i<m;i++){ if(board[i][0] == 'O') q.push(make_pair(i,0)); if(board[i][n-1] == 'O') q.push(make_pair(i,n-1)); } for(int j=0;j<n;j++){ if(board[0][j] == 'O') q.push(make_pair(0,j)); if(board[m-1][j] == 'O') q.push(make_pair(m-1,j)); } // BFS on all the elements in the queue while(!q.empty()){ pair<int,int> curr = q.front(); q.pop(); int x = curr.first, y = curr.second; if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O'){ board[x][y] = 'N'; // Marking all 'O' as 'N' as it is no longer surrounded by 'X' q.push(make_pair(x-1,y)); // Up q.push(make_pair(x+1,y)); // Down q.push(make_pair(x,y-1)); // Left q.push(make_pair(x,y+1)); // Right } } // Changing all 'O' to 'X' and all 'N' to 'O' for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j] == 'O') board[i][j] = 'X'; else if(board[i][j] == 'N') board[i][j] = 'O'; } } } };

Time complexity: O(m*n) as we are iterating through every cell in the matrix. Space complexity: O(m+n) as the maximum size of the queue can be m+n (for a boundary cell).

1