130. Surrounded Regions

📝 Problem Details

• Title: 130. Surrounded Regions
• Link: https://leetcode.com/problems/surrounded-regions/
• Difficulty: Medium
• Tags/Categories: Arrays Matrix DFS

💭What Were My Initial Thoughts?

- use a DFS approach where we:
	- start at the first element in the matrix and either go down or right 
	- if the value is an X, go down 
		- once you cant go down any further on the Xs path, "recurse" up and try moving right do this until you encounter an 'O' 
		- if you encounter an O, check if its an edge element , if its not convert it to an X and continue

🤔What Did I Struggle With?

1. directionality
	- initial approach only goes down and right, missing potential Os in the up and left direction
	- this may cause incomplete exploration

2. edge connection
	- initial approach flips all encountered Os to Xs unless they're edge elements
	- an O connected to an edge O (even indirectly) should not be flipped

3. revisits and efficiency
	- without marking visited cells, the above approach might repeatedly explore the same cells

💡 Explanation of Solution

Key Idea:
- Os that are completely surrounded by Xs should be flipped to X
- Os that are connected to any edge of the matrix should remain O

Approach:
- traverse the borders of the matrix and perform DFS to mark all edge-connected Os as safe by temporarily converting them to a marker value (e.g. T)
- after marking, traverse the entire matrix:
	- flip all unmarked Os to X (as they are surrounded)
	- restore all marked Ts back to O (as they are edge connected)

⌛ Complexity Analysis

Time Complexity: O(m*n)
- where m is the number of rows and n is the number of columns
- Each cell is visited at most once during the marking and flipping steps

Space Complexity: O(m*n)
- stack space for DFS recursive calls

💻 Implementation of Solution

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int rows = board.size();
        if (rows == 0) return;
        int cols = board[0].size();
 
        // Start DFS from borders
        for (int i = 0; i < rows; ++i) {
            if (board[i][0] == 'O') dfs(board, i, 0, rows, cols);
            if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1, rows, cols);
        }
        for (int j = 0; j < cols; ++j) {
            if (board[0][j] == 'O') dfs(board, 0, j, rows, cols);
            if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j, rows, cols);
        }
 
        // Flip remaining 'O's to 'X' and 'T's back to 'O'
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == 'T') board[i][j] = 'O';
            }
        }
    }
 
private:
    // Separate DFS function
    void dfs(vector<vector<char>>& board, int r, int c, int rows, int cols) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O') 
            return;
        board[r][c] = 'T'; // Mark as safe
        dfs(board, r + 1, c, rows, cols); // Down
        dfs(board, r - 1, c, rows, cols); // Up
        dfs(board, r, c + 1, rows, cols); // Right
        dfs(board, r, c - 1, rows, cols); // Left
    }
};