# Coloring A Border
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/coloring-a-border)
Canonical: https://scaleengineer.com/dsa/problems/coloring-a-border
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Booking.com](https://scaleengineer.com/companies/booking.com)
---
## 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_.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

**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`

# Approaches
## Two-Pass Traversal (BFS/DFS)
This approach tackles the problem by breaking it down into two distinct, sequential phases. First, it performs a graph traversal, such as Breadth-First Search (BFS) or Depth-First Search (DFS), to find all the cells that belong to the same connected component as the starting cell `(row, col)`. These cells are collected into a list. In the second phase, the algorithm iterates through this list of component cells to determine which ones qualify as border cells based on the problem's definition. Finally, these identified border cells are colored with the new color.
**Time:** O(M * N), where M and N are the grid dimensions. The first pass (BFS/DFS) visits each cell at most once, taking O(M * N) time in the worst case. The second pass iterates through the component cells (at most M*N) and performs a constant number of checks for each. The final coloring step is proportional to the number of border cells. Thus, the total time complexity is dominated by the grid traversal. · **Space:** O(M * N), where M and N are the grid dimensions. The space is dominated by the `visited` array, the `componentCells` list, and the BFS queue, all of which can grow to the size of the grid in the worst-case scenario.
**Pros:** The separation of concerns makes the code very clear and easy to reason about.; Debugging is simpler as each phase can be verified independently.
**Cons:** Requires extra space to store all cells of the component, which can be large.; Iterates over the component cells multiple times (once to find them, once to check for borders), making it slightly less performant than a single-pass solution.
### Explanation
The core idea is to separate the concern of finding the component from the concern of identifying its border. This makes the logic straightforward and easier to follow.

**Phase 1: Component Discovery**
A standard BFS/DFS starts from `(row, col)`. The traversal explores all reachable cells that share the same initial color. A `visited` array is used to prevent cycles and redundant processing. All discovered cells of the component are stored in a list, for example, `componentCells`.

**Phase 2: Border Identification and Coloring**
Once the entire component is known, the algorithm iterates through each cell in `componentCells`. For each cell, it checks if it meets the border criteria: being on the grid's physical boundary or being adjacent to a cell of a different color. The coordinates of cells that satisfy this condition are stored in another list, `borderCells`. After checking all component cells, a final loop goes through `borderCells` and applies the new `color` to the grid.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length;
        int n = grid[0].length;
        int originalColor = grid[row][col];

        if (originalColor == color) {
            return grid;
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        List<int[]> componentCells = new ArrayList<>();

        // Pass 1: Find all cells in the connected component
        queue.offer(new int[]{row, col});
        visited[row][col] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            componentCells.add(cell);

            for (int i = 0; i < 4; i++) {
                int nr = cell[0] + dr[i];
                int nc = cell[1] + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == originalColor) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        // Pass 2: Identify border cells from the component
        List<int[]> borderCells = new ArrayList<>();
        for (int[] cell : componentCells) {
            int r = cell[0];
            int c = cell[1];
            if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                borderCells.add(cell);
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (grid[nr][nc] != originalColor) {
                    borderCells.add(cell);
                    break;
                }
            }
        }

        // Color the border cells
        for (int[] cell : borderCells) {
            grid[cell[0]][cell[1]] = color;
        }

        return grid;
    }
}
```
### Algorithm
*   **Initialization:**
    1.  Get the dimensions of the grid, `m` and `n`.
    2.  Store the color of the starting cell `(row, col)` as `originalColor`.
    3.  If `originalColor` is the same as the new `color`, return the grid as no changes are needed.
    4.  Initialize a 2D boolean array `visited` of size `m x n` to keep track of visited cells.
    5.  Initialize a queue for BFS and a list `componentCells` to store all cells of the component.
*   **Pass 1: Find the Connected Component**
    1.  Add the starting cell `(row, col)` to the queue and mark it as visited.
    2.  Perform a standard BFS. While the queue is not empty, dequeue a cell.
    3.  Add the dequeued cell to `componentCells`.
    4.  For each of its four neighbors, if the neighbor is within grid bounds, has the `originalColor`, and has not been visited, mark it as visited and enqueue it.
*   **Pass 2: Identify and Store Border Cells**
    1.  Initialize a new list `borderCells`.
    2.  Iterate through each cell `(r, c)` in `componentCells`.
    3.  For each cell, determine if it's a border cell. A cell is on the border if it's on the physical edge of the grid (`r=0, r=m-1, c=0, or c=n-1`) or if it is adjacent to any cell with a color different from `originalColor`.
    4.  If the cell is identified as a border cell, add its coordinates to `borderCells`.
*   **Coloring**
    1.  Iterate through the `borderCells` list.
    2.  For each cell coordinate in the list, update the corresponding cell in the input `grid` with the new `color`.
*   **Return** the modified `grid`.

## Single-Pass Traversal (BFS/DFS)
This optimized approach integrates the component traversal and border identification into a single, efficient pass. Using a graph traversal algorithm like BFS or DFS, we explore the connected component starting from `(row, col)`. For each cell we visit, we immediately check if it qualifies as a border cell. The coordinates of any identified border cells are stored. After the traversal completes, a final step applies the new color to all the stored border cell locations.
**Time:** O(M * N). The algorithm visits each cell in the grid at most once. For each cell, it performs a constant number of operations (checking four neighbors). Therefore, the time complexity is linear with respect to the number of cells in the grid. · **Space:** O(M * N). In the worst-case scenario (e.g., a checkerboard pattern), the number of border cells can be proportional to the grid size. The `visited` array and the BFS queue also contribute O(M * N) space.
**Pros:** More efficient as it processes each component cell only once.; Can be more memory-efficient as it only needs to store border cells, not all component cells.
**Cons:** The logic within the main traversal loop is more complex as it combines traversal with border detection.; Still requires O(M * N) auxiliary space in the worst case for the visited set and traversal queue.
### Explanation
The key to this approach is to perform the border check for a cell at the same time it is being processed by the traversal algorithm. This avoids the need to store all component cells and re-iterate over them.

When the BFS algorithm processes a cell `(r, c)` from its queue, it examines all four of its neighbors. This examination serves two purposes:
1.  **Traversal:** To find other cells belonging to the component. If a neighbor has the same `originalColor` and hasn't been visited, it's added to the queue for future processing.
2.  **Border Detection:** To determine if the current cell `(r, c)` is on the border. If any neighbor is outside the grid's boundaries or has a color different from `originalColor`, it signifies that `(r, c)` is a border cell.

We collect all such border cells in a list. It's important to delay the actual coloring until the entire traversal is finished. Modifying the grid's colors mid-traversal would corrupt the `originalColor` checks for subsequent cells.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length, n = grid[0].length;
        int originalColor = grid[row][col];
        if (originalColor == color) {
            return grid;
        }

        List<int[]> borderCells = new ArrayList<>();
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];

        queue.offer(new int[]{row, col});
        visited[row][col] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];

            boolean isBorder = false;
            // Explore neighbors to find next cells for traversal AND check if current cell is a border
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    // If neighbor has the same color and is not visited, add to queue
                    if (grid[nr][nc] == originalColor) {
                        if (!visited[nr][nc]) {
                            visited[nr][nc] = true;
                            queue.offer(new int[]{nr, nc});
                        }
                    } else {
                        // Neighbor has a different color, so current cell is a border
                        isBorder = true;
                    }
                } else {
                    // Neighbor is out of bounds, so current cell is a border
                    isBorder = true;
                }
            }
            
            if (isBorder) {
                borderCells.add(cell);
            }
        }

        for (int[] cell : borderCells) {
            grid[cell[0]][cell[1]] = color;
        }

        return grid;
    }
}
```
### Algorithm
*   **Initialization:**
    1.  Get grid dimensions `m`, `n`, and the `originalColor` from `grid[row][col]`.
    2.  If `originalColor == color`, return the grid immediately.
    3.  Initialize a queue for BFS, a `visited` 2D array, and a list `borderCells` to store coordinates of border cells.
*   **Single Pass: Traversal and Border Identification**
    1.  Add the starting cell `(row, col)` to the queue and mark it as visited.
    2.  Begin the BFS loop. While the queue is not empty, dequeue a cell `(r, c)`.
    3.  For the current cell `(r, c)`, check if it's a border cell. This is done by inspecting its four neighbors:
        *   A neighbor that is out of the grid bounds makes `(r, c)` a border cell.
        *   An in-bounds neighbor with a color different from `originalColor` also makes `(r, c)` a border cell.
    4.  If `(r, c)` is determined to be a border cell, add its coordinates to the `borderCells` list.
    5.  Simultaneously, during the neighbor check, if an in-bounds neighbor has the `originalColor` and has not been visited, mark it as visited and add it to the queue to continue the traversal.
*   **Coloring:**
    1.  After the traversal is complete, iterate through the `borderCells` list.
    2.  For each coordinate pair, update the `grid` at that position with the new `color`.
*   **Return** the modified `grid`.

# Solutions
### Java

```java
class Solution {
private
  int[][] grid;
private
  int color;
private
  int m;
private
  int n;
private
  boolean[][] vis;
public
  int[][] colorBorder(int[][] grid, int row, int col, int color) {
    this.grid = grid;
    this.color = color;
    m = grid.length;
    n = grid[0].length;
    vis = new boolean[m][n];
    dfs(row, col, grid[row][col]);
    return grid;
  }
private
  void dfs(int i, int j, int c) {
    vis[i][j] = true;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n) {
        if (!vis[x][y]) {
          if (grid[x][y] == c) {
            dfs(x, y, c);
          } else {
            grid[i][j] = color;
          }
        }
      } else {
        grid[i][j] = color;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> colorBorder(vector<vector<int>> &grid, int row, int col,
                                  int color) {
    int m = grid.size();
    int n = grid[0].size();
    bool vis[m][n];
    memset(vis, false, sizeof(vis));
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<void(int, int, int)> dfs = [&](int i, int j, int c) {
      vis[i][j] = true;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          if (!vis[x][y]) {
            if (grid[x][y] == c) {
              dfs(x, y, c);
            } else {
              grid[i][j] = color;
            }
          }
        } else {
          grid[i][j] = color;
        }
      }
    };
    dfs(row, col, grid[row][col]);
    return grid;
  }
};

```

### Python

```python
class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]: def dfs(i: int, j: int, c: int) -> None: vis[i][j] = True for a, b in pairwise((- 1, 0, 1, 0, - 1)): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: if not vis[x][y]: if grid[x][y] == c: dfs(x, y, c) else: grid[i][j] = color else: grid[i][j] = color m, n = len(grid), len(grid[0]) vis = [[False] * n for _ in range(m)] dfs(row, col, grid[row][col]) return grid

```