> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/coloring-a-border.md).

# Coloring A Border

Given a 2-dimensional `grid` of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same *connected component* if and only if they have the same color and are next to each other in any of the 4 directions.

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

Given a square at location `(r0, c0)` in the grid and a `color`, color the border of the connected component of that square with the given `color`, and return the final `grid`.

**Example 1:**

```
Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
Output: [[3, 3], [3, 2]]
```

**Example 2:**

```
Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
Output: [[1, 3, 3], [2, 3, 3]]
```

**Example 3:**

```
Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]
```

**Note:**

1. `1 <= grid.length <= 50`
2. `1 <= grid[0].length <= 50`
3. `1 <= grid[i][j] <= 1000`
4. `0 <= r0 < grid.length`
5. `0 <= c0 < grid[0].length`
6. `1 <= color <= 1000`

```java
class Solution {
    public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { r0, c0 });
        int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
        // Marking the connected component
        int sameColor = grid[r0][c0];
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                int[] pos = q.poll();
                if (visited[pos[0]][pos[1]])
                    continue;
                visited[pos[0]][pos[1]] = true;
                for (int i = 0; i < 4; i++) {
                    int newX = pos[0] + dir[i][0], newY = pos[1] + dir[i][1];
                    if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length
                            && grid[newX][newY] == sameColor)
                        q.add(new int[] { newX, newY });
                }
            }
        }
        int[][] ans = new int[grid.length][grid[0].length];
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                // If this sq. belongs to our component
                if (visited[x][y]) {
                    if (x == 0 || x == grid.length - 1 || y == 0 || y == grid[0].length - 1)
                        ans[x][y] = color;
                    else {
                        boolean border = false;
                        for (int i = 0; i < 4; i++) {
                            int newX = x + dir[i][0], newY = y + dir[i][1];
                            if (!visited[newX][newY]) {
                                border = true;
                                break;
                            }
                        }
                        if (border)
                            ans[x][y] = color;
                        else
                            ans[x][y] = sameColor;
                    }
                } else
                    ans[x][y] = grid[x][y];
            }
        }
        return ans;
    }
}
```