Coloring A Border

• 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.

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.

1import java.util.ArrayList;2import java.util.LinkedList;3import java.util.List;4import java.util.Queue;5 6class Solution {7    public int[][] colorBorder(int[][] grid, int row, int col, int color) {8        int m = grid.length;9        int n = grid[0].length;10        int originalColor = grid[row][col];11 12        if (originalColor == color) {13            return grid;14        }15 16        Queue<int[]> queue = new LinkedList<>();17        boolean[][] visited = new boolean[m][n];18        List<int[]> componentCells = new ArrayList<>();19 20        // Pass 1: Find all cells in the connected component21        queue.offer(new int[]{row, col});22        visited[row][col] = true;23 24        int[] dr = {-1, 1, 0, 0};25        int[] dc = {0, 0, -1, 1};26 27        while (!queue.isEmpty()) {28            int[] cell = queue.poll();29            componentCells.add(cell);30 31            for (int i = 0; i < 4; i++) {32                int nr = cell[0] + dr[i];33                int nc = cell[1] + dc[i];34 35                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == originalColor) {36                    visited[nr][nc] = true;37                    queue.offer(new int[]{nr, nc});38                }39            }40        }41 42        // Pass 2: Identify border cells from the component43        List<int[]> borderCells = new ArrayList<>();44        for (int[] cell : componentCells) {45            int r = cell[0];46            int c = cell[1];47            if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {48                borderCells.add(cell);49                continue;50            }51            for (int i = 0; i < 4; i++) {52                int nr = r + dr[i];53                int nc = c + dc[i];54                if (grid[nr][nc] != originalColor) {55                    borderCells.add(cell);56                    break;57                }58            }59        }60 61        // Color the border cells62        for (int[] cell : borderCells) {63            grid[cell[0]][cell[1]] = color;64        }65 66        return grid;67    }68}

• 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.

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.

1import java.util.ArrayList;2import java.util.LinkedList;3import java.util.List;4import java.util.Queue;5 6class Solution {7    public int[][] colorBorder(int[][] grid, int row, int col, int color) {8        int m = grid.length, n = grid[0].length;9        int originalColor = grid[row][col];10        if (originalColor == color) {11            return grid;12        }13 14        List<int[]> borderCells = new ArrayList<>();15        Queue<int[]> queue = new LinkedList<>();16        boolean[][] visited = new boolean[m][n];17 18        queue.offer(new int[]{row, col});19        visited[row][col] = true;20 21        int[] dr = {-1, 1, 0, 0};22        int[] dc = {0, 0, -1, 1};23 24        while (!queue.isEmpty()) {25            int[] cell = queue.poll();26            int r = cell[0], c = cell[1];27 28            boolean isBorder = false;29            // Explore neighbors to find next cells for traversal AND check if current cell is a border30            for (int i = 0; i < 4; i++) {31                int nr = r + dr[i];32                int nc = c + dc[i];33 34                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {35                    // If neighbor has the same color and is not visited, add to queue36                    if (grid[nr][nc] == originalColor) {37                        if (!visited[nr][nc]) {38                            visited[nr][nc] = true;39                            queue.offer(new int[]{nr, nc});40                        }41                    } else {42                        // Neighbor has a different color, so current cell is a border43                        isBorder = true;44                    }45                } else {46                    // Neighbor is out of bounds, so current cell is a border47                    isBorder = true;48                }49            }50            51            if (isBorder) {52                borderCells.add(cell);53            }54        }55 56        for (int[] cell : borderCells) {57            grid[cell[0]][cell[1]] = color;58        }59 60        return grid;61    }62}