Coloring a border

Array Depth-First Search Breadth-First Search Matrix

51.1% acceptance

Feb 25, 2026

842

944

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn color_border(mut 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 visited = vec![vec![false; n]; m];
    let mut comp = vec![];
    let mut border = vec![];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((row as usize, col as usize));
    visited[row as usize][col as usize] = true;
    while let Some((r, c)) = queue.pop_front() {
      comp.push((r, c));
      let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
      let mut is_border = r == 0 || r == m-1 || c == 0 || c == n-1;
      for (dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nr >= m as i32 || nc < 0 || nc >= n as i32 {
          is_border = true;
        } else {
          let (nr, nc) = (nr as usize, nc as usize);
          if grid[nr][nc] != orig { is_border = true; }
          else if !visited[nr][nc] {
            visited[nr][nc] = true;
            queue.push_back((nr, nc));
          }
        }
      }
      if is_border { border.push((r, c)); }
    }
    for (r, c) in border { grid[r][c] = color; }
    grid
  }
}