Code Implementation

class Solution:
    def colorBorder(self, grid, row, col, color):
        m, n = len(grid), len(grid[0])
        orig_color = grid[row][col]
        visited = [[False] * n for _ in range(m)]
        borders = []

        def dfs(x, y):
            visited[x][y] = True
            is_border = False
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x+dx, y+dy
                if not (0 <= nx < m and 0 <= ny < n) or grid[nx][ny] != orig_color:
                    is_border = True
                elif not visited[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
      

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();
        int orig = grid[row][col];
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        vector<pair<int,int>> borders;
        vector<int> dx = {-1,1,0,0}, dy = {0,0,-1,1};
        function<void(int,int)> dfs = [&](int x, int y) {
            vis[x][y] = true;
            bool is_border = false;
            for(int d=0; d<4; ++d) {
                int nx = x+dx[d], ny = y+dy[d];
                if(nx<0 || nx>=m || ny<0 || ny>=n || grid[nx][ny]!=orig)
                    is_border = true;
                else if(!vis[nx][ny])
                    dfs(nx, ny);
            }
            if(is_border) borders.push_back({x,y});
        };
        dfs(row, col);
        for(auto& p : borders) grid[p.first][p.second]=color;
        return grid;
    }
};
      

class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length, n = grid[0].length;
        int orig = grid[row][col];
        boolean[][] vis = new boolean[m][n];
        List<int[]> borders = new ArrayList<>();
        int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
        dfs(grid, vis, borders, row, col, orig, dx, dy, m, n);
        for(int[] p : borders)
            grid[p[0]][p[1]] = color;
        return grid;
    }
    private void dfs(int[][] grid, boolean[][] vis, List<int[]> borders, int x, int y, int orig,
                     int[] dx, int[] dy, int m, int n) {
        vis[x][y] = true;
        boolean isBorder = false;
        for(int d=0; d<4; ++d) {
            int nx = x+dx[d], ny = y+dy[d];
            if(nx<0 || nx>=m || ny<0 || ny>=n || grid[nx][ny]!=orig)
                isBorder = true;
            else if(!vis[nx][ny])
                dfs(grid, vis, borders, nx, ny, orig, dx, dy, m, n);
        }
        if(isBorder) borders.add(new int[]{x, y});
    }
}
      

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

Problem Description

You are given a 2D grid of integers called grid, where each cell contains a color represented by an integer value. Also given are integers row, col, and color. The cell at position (row, col) is the starting point of a connected component: all cells connected 4-directionally (up, down, left, right) and having the same color as grid[row][col].

Your task is to color the border of this connected component with the new color. A border cell is defined as a cell in the component that is either:

• On the edge of the grid, or
• Next to a cell not in the component (i.e., not connected or of a different color)

Thought Process

At first glance, this problem resembles the classic "flood fill" or region coloring problem. The main difference is that we must only color the borders of the component, not the entire region.

A brute-force approach might be to color every cell in the component, but that would violate the requirement to color only the borders. Thus, we need a way to:

• Identify all cells that belong to the same component as (row, col)
• Determine which of these are border cells

The challenge is to efficiently traverse the component, mark border cells, and avoid recoloring internal cells or cells outside the component. Using a visited matrix will help us avoid revisiting cells, and checking the four neighbors of each cell will help us decide if a cell is a border.

Solution Approach

We can solve this problem using Depth-First Search (DFS). Here's a step-by-step breakdown:

1. Initialize:
   • Store the original color of the starting cell.
   • Create a visited matrix to keep track of cells we've already processed.
   • Maintain a list to collect border cells.
2. DFS Traversal:
   • Start DFS from the given (row, col).
   • For each cell, mark it as visited.
   • For each of the four directions, check the neighbor:
     • If the neighbor is out of bounds or has a different color, mark the current cell as a border cell.
     • If the neighbor is within bounds and the same color, continue DFS if it hasn't been visited.
   • If the cell is a border, add it to the border list.
3. Coloring:
   • After DFS, loop through all border cells and set their color to the given new color.
4. Return:
   • Return the modified grid.

This approach ensures that only the border cells of the connected component are colored, and no cell is colored more than once. The use of a visited matrix ensures we do not revisit or recolor any cell.

Example Walkthrough

Let's consider the following example:

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

1. The component connected to (0,0) consists of cells (0,0), (0,1), and (1,0), all with color 1.
2. For each cell, check if it's a border:
   • (0,0): On the top and left edge of the grid → border
   • (0,1): On the top and right edge → border
   • (1,0): On the left edge, and its neighbor (1,1) is color 2 (different) → border
3. All three cells are border cells. We color them with 3.
4. Result:
   [[3,3],[3,2]]

The solution only colors the border cells, leaving any non-component or internal cells unchanged.

Time and Space Complexity

Brute-force approach:
If we tried to color every cell and then backtrack, the time and space complexity could be as high as O(m*n) for an m x n grid, with redundant work.

Optimized DFS approach:

• Time Complexity: O(m*n) in the worst case, since we may visit every cell in the grid once (if the component covers the whole grid).
• Space Complexity: O(m*n) for the visited matrix and, in the worst case, the recursion stack and border list.

These complexities are optimal, as we must at least visit every component cell to determine its border status.

Summary

The "Coloring A Border" problem is a twist on classic region-filling algorithms. The key insight is to use DFS to both identify the connected component and determine which of its cells are borders. By carefully marking visited cells and checking neighbors, we can efficiently collect and recolor only the required border cells. This approach is clean, avoids unnecessary coloring, and demonstrates how classic traversal techniques can be adapted to solve nuanced grid problems.