Watch 10 video solutions for Coloring A Border, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by Pepcoding has 42,663 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.
Two squares are called adjacent if they are next to each other in any of the 4 directions.
Two squares belong to the same connected component if they have the same color and they are adjacent.
The border of a connected component is all the squares in the connected component that are either adjacent to (at least) a square not in the component, or on the boundary of the grid (the first or last row or column).
You should color the border of the connected component that contains the square grid[row][col] with color.
Return the final grid.
Example 1:
Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3 Output: [[3,3],[3,2]]
Example 2:
Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3 Output: [[1,3,3],[2,3,3]]
Example 3:
Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2 Output: [[2,2,2],[2,1,2],[2,2,2]]
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j], color <= 10000 <= row < m0 <= col < nProblem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Preferred for interviews and recursive grid traversal problems |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Useful when avoiding recursion depth or when iterative traversal is preferred |