Coloring A Border - Solution & Explanation

Problem Overview: You are given a grid of colors and a starting cell. The task is to find the connected component that shares the same color as the starting cell and repaint only its border cells with a new color. A border cell is one that touches the grid boundary or has at least one neighboring cell with a different color.

Approach 1: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))

This approach treats the grid like a graph where each cell connects to its four neighbors. Starting from (row, col), run a DFS to visit all cells belonging to the same connected component. While exploring neighbors, determine whether the current cell lies on the border by checking if it touches the grid boundary or if any adjacent cell has a different color. Border cells are collected in a list (or marked temporarily) and recolored after traversal. DFS works well here because recursion naturally explores connected regions, making it easy to track visited cells and inspect neighbors. The extra space comes from the recursion stack and the visited structure.

DFS solutions commonly rely on a visited matrix or temporarily marking cells to avoid revisiting. Each cell is processed at most once, giving linear complexity relative to the grid size. If you want to strengthen your understanding of recursive grid traversal, review Depth-First Search and common patterns in matrix problems.

Approach 2: Breadth-First Search (BFS) Traversal (Time: O(m*n), Space: O(m*n))

BFS solves the same connected-component problem using a queue instead of recursion. Begin by pushing the starting cell into a queue and expanding level by level. For each cell, inspect the four directions and enqueue neighbors with the same original color that have not been visited. During processing, check whether the current cell touches the boundary or has a neighbor with a different color. If so, mark it as a border candidate.

After BFS finishes exploring the component, update the stored border cells with the new color. BFS is iterative and avoids recursion depth issues, which can be helpful for very large grids. The algorithm still visits each cell once and performs constant neighbor checks, resulting in O(m*n) time complexity and O(m*n) space due to the queue and visited tracking. This pattern is common in Breadth-First Search problems involving grid components.

Recommended for interviews: Both DFS and BFS are accepted optimal solutions with identical complexity. Interviewers usually expect a DFS implementation because it is shorter and highlights your ability to reason about connected components in a grid. Showing the BFS variant demonstrates understanding of traversal tradeoffs and queue-based graph exploration.