SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to capture all regions surrounded by 'X' on a 2D board. A region is captured by flipping all 'O's into 'X's in that surrounded region. Any 'O' connected to a border cannot be flipped to 'X' as it is not fully surrounded.

Intuition

The key intuition is to recognize that only the 'O's that are not connected to the border will be surrounded and need to be flipped to 'X'. We can use Depth-First Search (DFS) to mark all 'O's connected to the border and then flip the remaining 'O's that are fully surrounded.

Approach

1. Initialize the board dimensions: Determine the number of rows and columns.
2. Define directions: Set up the four possible movement directions (right, down, left, up) to use in DFS.
3. Depth-First Search (DFS) function: Create a helper function dfs that will mark 'O's connected to the border by changing them to 'Y'.
4. Traverse borders and apply DFS: Iterate over the border cells of the board. If a cell contains 'O', apply DFS to mark all connected 'O's.
5. Convert inner 'O's to 'X's: Traverse the entire board and change all remaining 'O's to 'X' because these are the ones surrounded by 'X's.
6. Restore border-connected 'O's: Finally, traverse the board again to convert all 'Y's back to 'O's to restore the original 'O's that were connected to the border.

Complexity

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.

Space Complexity:

O(m * n) in the worst case due to the recursion stack in DFS.

Code

C++

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        vector<vector<int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
        function<void(int, int)> dfs = [&](int i, int j) {
            board[i][j] = 'Y';
            for (const auto& d : dir) {
                int ix = i + d[0];
                int jy = j + d[1];
                if (ix > 0 && ix < m - 1 && jy > 0 && jy < n - 1 && board[ix][jy] == 'O') {
                    dfs(ix, jy);
                }
            }
        };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    if (board[i][j] == 'O') dfs(i, j);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'Y') board[i][j] = 'O';
            }
        }
    }
};

Python

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return
        
        m, n = len(board), len(board[0])
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        
        def dfs(i, j):
            board[i][j] = 'Y'
            for x, y in directions:
                ix, jy = i + x, j + y
                if 0 <= ix < m and 0 <= jy < n and board[ix][jy] == 'O':
                    dfs(ix, jy)
        
        # Traverse borders to find 'O's
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    if board[i][j] == 'O':
                        dfs(i, j)
        
        # Replace all 'O's with 'X's
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
        
        # Replace all 'Y's back to 'O's
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'Y':
                    board[i][j] = 'O'

Java

class Solution {
    private void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        board[i][j] = 'Y';
        for (int[] d : dir) {
            int ix = i + d[0];
            int jy = j + d[1];
            if (ix > 0 && ix < m - 1 && jy > 0 && jy < n - 1 && board[ix][jy] == 'O') {
                dfs(board, ix, jy);
            }
        }
    }
    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        int n = board[0].length;
        // Traverse borders to find 'O's
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    if (board[i][j] == 'O') dfs(board, i, j);
                }
            }
        }
        // Replace all 'O's with 'X's
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
        // Replace all 'Y's back to 'O's
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'Y') board[i][j] = 'O';
            }
        }
    }
}

JavaScript

var solve = function(board) {
    const m = board.length;
    const n = board[0].length;
    const dir = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    function dfs(i, j) {
        board[i][j] = "Y";
        for(const [x,y] of dir) {
            const ix = i + x;
            const jy = j + y;
                console.log(ix, jy, i, j, x, y);
            if(ix > 0 && ix < m - 1 && jy > 0 && jy < n - 1 && board[ix][jy] === "O") {
                dfs(ix, jy);
            }
        }
    }
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(i === 0 || i === m - 1 || j === 0 || j === n - 1) {
                if(board[i][j] === "O") dfs(i,j);
            }
        }
    }
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(board[i][j] === "O") board[i][j] = "X";
        }
    }
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(board[i][j] === "Y") board[i][j] = "O";
        }
    }
    return board;
};