Coloring A Border

medium grid dfs connected component

Problem

You are given an m x n integer grid where grid[i][j] is the color of the cell. Starting from cell (row, col), the connected component is the maximal set of cells with the same color reachable through up/down/left/right moves. A cell is on the border of the component if it touches the grid edge or is adjacent to a cell outside the component. Recolor every border cell of the component containing (row, col) to the given color and return the grid.

Inputgrid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3

Output[[1,3,3],[2,3,3]]

The component of 2s reachable from (0,1) is every 2 except the bottom-left one. All of those 2s are border cells, so they become 3.

grid (rows separated by ; values by ,)

row

col

color

def color_border(grid, row, col, color):
    m, n = len(grid), len(grid[0])
    start = grid[row][col]
    seen = set()
    border = []

    def dfs(r, c):
        seen.add((r, c))
        is_border = False
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] != start:
                is_border = True
            elif (nr, nc) not in seen:
                dfs(nr, nc)
        if is_border:
            border.append((r, c))

    dfs(row, col)
    for r, c in border:
        grid[r][c] = color
    return grid

function colorBorder(grid, row, col, color) {
  const m = grid.length, n = grid[0].length;
  const start = grid[row][col];
  const seen = new Set();
  const border = [];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function dfs(r, c) {
    seen.add(r + "," + c);
    let isBorder = false;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] !== start) {
        isBorder = true;
      } else if (!seen.has(nr + "," + nc)) {
        dfs(nr, nc);
      }
    }
    if (isBorder) border.push([r, c]);
  }

  dfs(row, col);
  for (const [r, c] of border) grid[r][c] = color;
  return grid;
}

class Solution {
    int m, n, start;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    boolean[][] seen;
    List<int[]> border = new ArrayList<>();

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        m = grid.length; n = grid[0].length;
        start = grid[row][col];
        seen = new boolean[m][n];
        dfs(grid, row, col);
        for (int[] p : border) grid[p[0]][p[1]] = color;
        return grid;
    }

    void dfs(int[][] grid, int r, int c) {
        seen[r][c] = true;
        boolean isBorder = false;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != start) {
                isBorder = true;
            } else if (!seen[nr][nc]) {
                dfs(grid, nr, nc);
            }
        }
        if (isBorder) border.add(new int[]{r, c});
    }
}

class Solution {
    int m, n, start;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<bool>> seen;
    vector<pair<int,int>> border;

    void dfs(vector<vector<int>>& grid, int r, int c) {
        seen[r][c] = true;
        bool isBorder = false;
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != start) {
                isBorder = true;
            } else if (!seen[nr][nc]) {
                dfs(grid, nr, nc);
            }
        }
        if (isBorder) border.push_back({r, c});
    }
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        m = grid.size(); n = grid[0].size();
        start = grid[row][col];
        seen.assign(m, vector<bool>(n, false));
        dfs(grid, row, col);
        for (auto& p : border) grid[p.first][p.second] = color;
        return grid;
    }
};

Explanation

We must recolor only the edge cells of one connected blob of same-colored cells, leaving its interior alone. The plan is a DFS flood fill that visits the whole blob but flags which cells are on the border.

Starting from (row, col), we remember its color as start and explore the four neighbours. A cell is a border cell if any neighbour is off the grid or has a different color — that means it sits on the boundary of the component.

We collect border cells in a list during the DFS and only recolor them after the search finishes. This delay matters: changing colors mid-search would confuse the grid[nr][nc] != start checks for cells we haven't visited yet.

Example: grid=[[1,2,2],[2,3,2]], row=0, col=1, color=3. The component of 2s reachable from (0,1) is every 2 except the bottom-left one; all of them touch the edge or a non-2 cell, so they all turn into 3, giving [[1,3,3],[2,3,3]].

Time: O(m·n) Space: O(m·n)