Problem

You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.

Two squares are called adjacent if they are next to each other in any of the 4 directions.

Two squares belong to the same connected component if they have the same color and they are adjacent.

The border of a connected component is all the squares in the connected component that are either adjacent to (at least) a square not in the component, or on the boundary of the grid (the first or last row or column).

You should color the border of the connected component that contains the square grid[row][col] with color.

Return the final grid.

Examples

Example 1

1
2

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

Example 2

1
2

Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]

Example 3

1
2

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
Output: [[2,2,2],[2,1,2],[2,2,2]]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j], color <= 1000
  • 0 <= row < m
  • 0 <= col < n

Solution

Method 1 – DFS (Mark and Color Border)

Intuition

We use DFS to find all cells in the connected component. For each cell, we check if it is a border (adjacent to a different color or on the grid boundary). We mark border cells and finally color them.

Approach

  1. Use DFS to visit all cells in the connected component starting from (row, col).
  2. For each cell, check if it is a border:
    • It is on the grid boundary, or
    • It is adjacent to a cell not in the component.
  3. Mark border cells in a set or with a special value.
  4. After DFS, color all border cells with the given color.
  5. Return the modified grid.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        int m = grid.size(), n = grid[0].size(), orig = grid[row][col];
        vector<vector<int>> vis(m, vector<int>(n));
        vector<pair<int, int>> borders;
        function<void(int, int)> dfs = [&](int x, int y) {
            vis[x][y] = 1;
            bool isBorder = false;
            for (auto [dx, dy] : vector<pair<int,int>>{{0,1},{1,0},{0,-1},{-1,0}}) {
                int nx = x + dx, ny = y + dy;
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != orig) isBorder = true;
                else if (!vis[nx][ny]) dfs(nx, ny);
            }
            if (isBorder) borders.push_back({x, y});
        };
        dfs(row, col);
        for (auto& [x, y] : borders) grid[x][y] = color;
        return grid;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func colorBorder(grid [][]int, row, col, color int) [][]int {
    m, n := len(grid), len(grid[0])
    orig := grid[row][col]
    vis := make([][]bool, m)
    for i := range vis { vis[i] = make([]bool, n) }
    borders := [][2]int{}
    var dfs func(int, int)
    dfs = func(x, y int) {
        vis[x][y] = true
        isBorder := false
        dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
        for _, d := range dirs {
            nx, ny := x+d[0], y+d[1]
            if nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != orig {
                isBorder = true
            } else if !vis[nx][ny] {
                dfs(nx, ny)
            }
        }
        if isBorder {
            borders = append(borders, [2]int{x, y})
        }
    }
    dfs(row, col)
    for _, b := range borders {
        grid[b[0]][b[1]] = color
    }
    return grid
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length, n = grid[0].length, orig = grid[row][col];
        boolean[][] vis = new boolean[m][n];
        List<int[]> borders = new ArrayList<>();
        dfs(grid, row, col, orig, vis, borders);
        for (int[] b : borders) grid[b[0]][b[1]] = color;
        return grid;
    }
    void dfs(int[][] grid, int x, int y, int orig, boolean[][] vis, List<int[]> borders) {
        vis[x][y] = true;
        int m = grid.length, n = grid[0].length;
        boolean isBorder = false;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != orig) isBorder = true;
            else if (!vis[nx][ny]) dfs(grid, nx, ny, orig, vis, borders);
        }
        if (isBorder) borders.add(new int[]{x, y});
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun colorBorder(grid: Array<IntArray>, row: Int, col: Int, color: Int): Array<IntArray> {
        val m = grid.size; val n = grid[0].size; val orig = grid[row][col]
        val vis = Array(m) { BooleanArray(n) }
        val borders = mutableListOf<Pair<Int, Int>>()
        fun dfs(x: Int, y: Int) {
            vis[x][y] = true
            var isBorder = false
            val dirs = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
            for ((dx, dy) in dirs) {
                val nx = x + dx; val ny = y + dy
                if (nx !in 0 until m || ny !in 0 until n || grid[nx][ny] != orig) isBorder = true
                else if (!vis[nx][ny]) dfs(nx, ny)
            }
            if (isBorder) borders.add(x to y)
        }
        dfs(row, col)
        for ((x, y) in borders) grid[x][y] = color
        return grid
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def colorBorder(self, grid: list[list[int]], row: int, col: int, color: int) -> list[list[int]]:
        m, n = len(grid), len(grid[0])
        orig = grid[row][col]
        vis = [[False]*n for _ in range(m)]
        borders = []
        def dfs(x: int, y: int):
            vis[x][y] = True
            is_border = False
            for dx, dy in ((0,1),(1,0),(0,-1),(-1,0)):
                nx, ny = x+dx, y+dy
                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] != orig:
                    is_border = True
                elif not vis[nx][ny]:
                    dfs(nx, ny)
            if is_border:
                borders.append((x, y))
        dfs(row, col)
        for x, y in borders:
            grid[x][y] = color
        return grid
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn color_border(grid: Vec<Vec<i32>>, row: i32, col: i32, color: i32) -> Vec<Vec<i32>> {
        let m = grid.len();
        let n = grid[0].len();
        let orig = grid[row as usize][col as usize];
        let mut vis = vec![vec![false; n]; m];
        let mut borders = vec![];
        fn dfs(x: usize, y: usize, m: usize, n: usize, orig: i32, grid: &Vec<Vec<i32>>, vis: &mut Vec<Vec<bool>>, borders: &mut Vec<(usize, usize)>) {
            vis[x][y] = true;
            let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
            let mut is_border = false;
            for (dx, dy) in dirs.iter() {
                let nx = x as i32 + dx;
                let ny = y as i32 + dy;
                if nx < 0 || nx >= m as i32 || ny < 0 || ny >= n as i32 || grid[nx as usize][ny as usize] != orig {
                    is_border = true;
                } else if !vis[nx as usize][ny as usize] {
                    dfs(nx as usize, ny as usize, m, n, orig, grid, vis, borders);
                }
            }
            if is_border {
                borders.push((x, y));
            }
        }
        dfs(row as usize, col as usize, m, n, orig, &grid, &mut vis, &mut borders);
        let mut grid = grid;
        for (x, y) in borders {
            grid[x][y] = color;
        }
        grid
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    colorBorder(grid: number[][], row: number, col: number, color: number): number[][] {
        const m = grid.length, n = grid[0].length, orig = grid[row][col];
        const vis = Array.from({length: m}, () => Array(n).fill(false));
        const borders: [number, number][] = [];
        function dfs(x: number, y: number) {
            vis[x][y] = true;
            let isBorder = false;
            for (const [dx, dy] of [[0,1],[1,0],[0,-1],[-1,0]]) {
                const nx = x + dx, ny = y + dy;
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] !== orig) isBorder = true;
                else if (!vis[nx][ny]) dfs(nx, ny);
            }
            if (isBorder) borders.push([x, y]);
        }
        dfs(row, col);
        for (const [x, y] of borders) grid[x][y] = color;
        return grid;
    }
}

Complexity

  • ⏰ Time complexity: O(mn)
  • 🧺 Space complexity: O(mn)