Coloring A Border

Coloring A Border

What is this problem about?

The Coloring A Border interview question asks you to identify and recolor the "border" of a specific connected component in a grid. You are given a grid, a starting cell (row, col), and a newColor. The component consists of all cells reachable from the start that have the same original color. A cell in this component is on the "border" if it is at the edge of the grid or if it is adjacent to a cell of a different color.

Why is this asked in interviews?

Microsoft and Google use the Matrix interview pattern to evaluate your grid traversal skills. It’s a twist on the classic "Flood Fill" algorithm. While Flood Fill colors the entire area, this problem requires you to apply specific logic to determine which cells within the area should be modified. It tests your ability to maintain state (which cells have been visited) while checking neighbors for color boundaries.

Algorithmic pattern used

This problem is best solved using Breadth-First Search (BFS) or Depth-First Search (DFS).

1. Identify all cells in the component.
2. For each cell in the component, check its 4 neighbors.
3. If a neighbor is outside the grid OR has a different color than the original, the current cell is a border cell.
4. Store all border cells in a list and recolor them at the very end (to avoid interfering with the color checks of other cells).

Example explanation

Grid: 1 1 1 1 1 1 1 1 1 Target: (1, 1) (center), newColor = 2.

1. Original color is 1. The whole grid is the component.
2. Cell (0, 0) is a border because it's at the edge.
3. Cell (1, 1) (center) is NOT a border because all 4 neighbors are inside and have color 1.
4. Only the outer ring of 1s will be colored 2.

Common mistakes candidates make

• Immediate Coloring: Coloring a cell as soon as you find it's a border. This changes the color for neighboring checks, leading to incorrect border identification.
• Visited Set: Forgetting to track visited cells, which leads to infinite loops in connected components.
• Incorrect Border Definition: Missing the condition that edges of the grid are automatically borders.

Interview preparation tip

When modifying a grid based on neighborhood properties, always separate the "identification" phase from the "modification" phase. This ensures that the state of the grid remains consistent throughout the traversal.