#1034

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Coloring A Border

Given a grid and a starting cell, color all border cells of the connected component using DFS while preserving interior colors.

array depth first search breadth first search matrix

Problem Statement

You are given an m x n integer matrix grid and three integers row, col, and color. Each grid cell has an initial color, and two cells are adjacent if they are next to each other horizontally or vertically. The goal is to identify the connected component containing the cell at (row, col) and modify its border cells.

A border cell is any cell in the connected component that has at least one adjacent neighbor outside the component or outside the grid. Update all border cells to the given color while leaving interior cells unchanged. Return the resulting grid after coloring the border appropriately.

Examples

Example 1

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

Output: [[3,3],[3,2]]

Example details omitted.

Example 2

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

Output: [[1,3,3],[2,3,3]]

Example details omitted.

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]]

Example details omitted.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j], color <= 1000
0 <= row < m
0 <= col < n

Solution Approach

Depth-First Search Traversal

Perform a DFS starting from the given cell to explore the entire connected component. Track visited cells to prevent infinite loops and for each cell, check its neighbors to determine if it is a border cell. Collect all border cells during traversal.

Mark and Color Borders

After DFS traversal, iterate over all identified border cells and update their color to the target value. Interior cells remain unchanged, ensuring only the true borders are colored.

Alternative BFS Approach

Use a queue for BFS to traverse the component level by level. Mark border cells similarly by checking neighboring positions, then color all collected border cells. BFS can offer easier iterative control compared to recursion in DFS.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) in the worst case because every cell might be visited once. Space complexity is O(m n) due to the recursion stack in DFS or queue in BFS and storage of border cells.

What Interviewers Usually Probe

Focuses on DFS implementation details and border detection logic.
Checks handling of edge cases where the component touches the grid boundary.
May probe iterative vs recursive DFS/BFS trade-offs for array traversal.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check grid boundaries, which causes out-of-bounds errors.
Incorrectly coloring interior cells instead of only borders.
Revisiting cells without marking them, causing infinite recursion or excess work.

Follow-up variants

Coloring multiple disconnected components simultaneously with different target colors.
Allowing diagonal adjacency for connected components instead of only 4-directional.
Finding the smallest or largest border length after coloring without modifying the grid.

FAQ

What defines a border cell in Coloring A Border?

A border cell has at least one adjacent neighbor outside the connected component or outside the grid, which determines if it should be recolored.

Can I use BFS instead of DFS for this problem?

Yes, BFS can be used to traverse the connected component and identify border cells iteratively instead of using recursion.

How do I avoid coloring interior cells accidentally?

Track all cells during traversal and mark only those with neighbors outside the component or grid as border cells before coloring.

What is the time complexity for Coloring A Border?

The time complexity is O(m*n) in the worst case if every cell is visited once, and space complexity depends on DFS recursion or BFS queue size.

Does the problem pattern relate specifically to arrays and DFS?

Yes, the main pattern is array traversal with DFS to find connected components and selectively color border cells, which is the core challenge.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def colorBorder(
        self, grid: List[List[int]], row: int, col: int, color: int
    ) -> List[List[int]]:
        def dfs(i: int, j: int, c: int) -> None:
            vis[i][j] = True
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n:
                    if not vis[x][y]:
                        if grid[x][y] == c:
                            dfs(x, y, c)
                        else:
                            grid[i][j] = color
                else:
                    grid[i][j] = color

        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]
        dfs(row, col, grid[row][col])
        return grid

Continue Practicing

#1020 number of enclaves #959 regions cut by slashes #934 shortest bridge