LeetCode 1034 - Coloring A Border

The problem gives us a two dimensional grid where each cell contains an integer representing a color. We are also given a starting position, (row, col), and a new color value. The cell at grid[row][col] belongs to some connected component.

leetcodemediumarraydepth-first-searchbreadth-first-searchmatrix

LeetCode Problem 1034

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional grid where each cell contains an integer representing a color. We are also given a starting position, (row, col), and a new color value.

The cell at grid[row][col] belongs to some connected component. A connected component is formed by cells that:

  • Have the same original color
  • Are connected through up, down, left, or right moves

The task is not to recolor the entire component. Instead, we only recolor the border cells of that component.

A cell is considered part of the border if either:

  • It lies on the outer edge of the grid
  • At least one of its four neighbors is not part of the same connected component

Every non-border cell inside the component must keep its original color.

The output should be the modified grid after recoloring only the border cells.

The constraints are relatively small:

  • m, n <= 50
  • Total cells are at most 2500

This means a graph traversal solution such as Depth-First Search (DFS) or Breadth-First Search (BFS) is completely feasible. Even an O(m * n) traversal is efficient enough.

There are several important edge cases to consider.

If the connected component contains only one cell, then that cell is automatically a border because it touches the boundary of the component. It must be recolored.

If the entire component fills the whole grid, then only the outer ring is recolored while interior cells remain unchanged.

If the new color is the same as the original color, we still need to correctly identify border cells, although the final grid may visually remain unchanged.

Another subtle case occurs when we recolor cells while traversing. If we immediately overwrite cell values, we may accidentally break future connectivity checks. Because of this, we must either:

  • Keep a separate visited structure
  • Delay recoloring until after traversal
  • Use temporary markers carefully

Approaches

Brute Force Approach

A brute force strategy would try to determine for every cell in the grid whether it belongs to the connected component and whether it is a border.

One possible implementation is:

  1. Start from (row, col) and collect all cells in the connected component.
  2. For every cell in the component, examine its four neighbors.
  3. If any neighbor is outside the grid or has a different color, mark the cell as a border.
  4. Recolor all marked border cells.

This approach is actually already efficient enough for the constraints, because the grid is small. However, if implemented naively, it may repeatedly scan cells or perform redundant connectivity checks.

For example, a poorly designed brute force method might run a fresh DFS from every cell to verify connectivity, leading to significantly worse complexity.

Optimal Approach

The key observation is that the problem is fundamentally a graph traversal problem.

The connected component can be explored directly using DFS or BFS starting from (row, col). During traversal, we can determine whether each visited cell is a border.

A cell is a border if:

  • It lies on the edge of the matrix
  • Or one of its neighbors has a different original color

The optimal solution performs a single traversal of the component and stores border cells separately. After traversal finishes, only those border cells are recolored.

This avoids modifying the grid during traversal, which keeps neighbor checks accurate.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) May repeatedly recompute connectivity
Optimal O(m * n) O(m * n) Single DFS/BFS traversal of component

Algorithm Walkthrough

Step 1: Store the Original Color

We first save the color of the starting cell:

original_color = grid[row][col]

This is important because every cell in the connected component must match this color.

Step 2: Create Supporting Structures

We maintain:

  • A visited matrix to avoid revisiting cells
  • A list called borders to store cells that must be recolored

The visited matrix prevents infinite recursion and redundant work.

Step 3: Start DFS Traversal

We run DFS beginning from (row, col).

For every visited cell:

  1. Mark it as visited.
  2. Examine all four neighboring directions.

Step 4: Determine Whether the Cell Is a Border

For each neighbor:

  • If the neighbor is outside the grid, the current cell is a border.
  • If the neighbor exists but has a different color, the current cell is also a border.
  • If the neighbor has the same original color and has not been visited, continue DFS into it.

We use a boolean flag such as is_border.

Step 5: Record Border Cells

After checking all neighbors:

  • If is_border is true, append the cell coordinates to borders.

We do not recolor immediately because changing values early could interfere with later neighbor checks.

Step 6: Recolor Border Cells

After DFS completes:

  • Iterate through all cells stored in borders
  • Set each cell to the new color

Step 7: Return the Grid

Finally, return the modified grid.

Why it works

The DFS visits every cell in the connected component exactly once. For each visited cell, we correctly determine whether it belongs to the border by checking adjacency conditions.

Interior cells are never recolored because all four neighbors belong to the same component and remain inside the grid. Border cells are recolored because they either touch the grid boundary or touch a cell outside the component.

Since recoloring happens only after traversal completes, all connectivity checks use the original grid values, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def colorBorder(
        self,
        grid: List[List[int]],
        row: int,
        col: int,
        color: int
    ) -> List[List[int]]:

        rows = len(grid)
        cols = len(grid[0])

        original_color = grid[row][col]

        visited = [[False] * cols for _ in range(rows)]
        borders = []

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int) -> None:
            visited[r][c] = True

            is_border = False

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                # Outside the grid
                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    is_border = True

                # Different color neighbor
                elif grid[nr][nc] != original_color:
                    is_border = True

                # Continue DFS
                elif not visited[nr][nc]:
                    dfs(nr, nc)

            if is_border:
                borders.append((r, c))

        dfs(row, col)

        for r, c in borders:
            grid[r][c] = color

        return grid

The implementation begins by storing the dimensions of the grid and the original component color. This original color acts as the identifier for the connected component.

A visited matrix is used to ensure each component cell is processed only once. The borders list stores coordinates that should eventually be recolored.

The DFS function recursively explores neighboring cells. For every neighbor, it checks whether the neighbor lies outside the grid or has a different color. Either condition means the current cell belongs to the border.

If a neighboring cell shares the same original color and has not yet been visited, DFS continues into that neighbor.

Importantly, the algorithm does not recolor cells during traversal. Instead, it records border cells first and recolors afterward. This guarantees that all connectivity checks use the original grid state.

Finally, every recorded border cell is updated to the target color, and the modified grid is returned.

Go Solution

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
	rows := len(grid)
	cols := len(grid[0])

	originalColor := grid[row][col]

	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}

	borders := make([][2]int, 0)

	directions := [][2]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	var dfs func(int, int)

	dfs = func(r int, c int) {
		visited[r][c] = true

		isBorder := false

		for _, dir := range directions {
			nr := r + dir[0]
			nc := c + dir[1]

			if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
				isBorder = true
			} else if grid[nr][nc] != originalColor {
				isBorder = true
			} else if !visited[nr][nc] {
				dfs(nr, nc)
			}
		}

		if isBorder {
			borders = append(borders, [2]int{r, c})
		}
	}

	dfs(row, col)

	for _, cell := range borders {
		r := cell[0]
		c := cell[1]
		grid[r][c] = color
	}

	return grid
}

The Go implementation follows the same logical structure as the Python version. The main difference is that Go requires explicit allocation of the visited matrix and uses slices instead of Python lists.

The DFS function is implemented as a closure so it can recursively access shared variables like grid, visited, and borders.

Coordinates are stored as fixed-size arrays [2]int, which is a lightweight and efficient representation.

Integer overflow is not a concern because grid dimensions are very small.

Worked Examples

Example 1

Input:

grid = [[1,1],
        [1,2]]

row = 0
col = 0
color = 3

The connected component contains:

(0,0), (0,1), (1,0)

DFS Traversal

Cell Border Reason Border?
(0,0) Touches top and left edge Yes
(0,1) Adjacent to value 2 Yes
(1,0) Touches bottom and left edge Yes

Border cells collected:

[(0,0), (0,1), (1,0)]

After recoloring:

[[3,3],
 [3,2]]

Example 2

Input:

grid = [[1,2,2],
        [2,3,2]]

row = 0
col = 1
color = 3

Connected component:

(0,1), (0,2), (1,2)

Border Detection

Cell Border Reason
(0,1) Top edge
(0,2) Top and right edge
(1,2) Right edge

All component cells are borders.

Final grid:

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

The entire grid forms one component.

Interior vs Border

Cell Border?
(0,0) Yes
(0,1) Yes
(0,2) Yes
(1,0) Yes
(1,1) No
(1,2) Yes
(2,0) Yes
(2,1) Yes
(2,2) Yes

Only the center remains unchanged.

Final grid:

[[2,2,2],
 [2,1,2],
 [2,2,2]]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited at most once
Space O(m * n) Visited matrix and recursion stack

The DFS traversal processes each component cell exactly one time. Every neighbor check is constant time, so total work is proportional to the number of grid cells.

The space complexity comes from two sources:

  • The visited matrix
  • The recursion stack in the worst case where the component contains every cell

Since the grid size is bounded by 50 x 50, this is completely acceptable.

Test Cases

from typing import List

class Solution:
    def colorBorder(
        self,
        grid: List[List[int]],
        row: int,
        col: int,
        color: int
    ) -> List[List[int]]:

        rows = len(grid)
        cols = len(grid[0])

        original_color = grid[row][col]

        visited = [[False] * cols for _ in range(rows)]
        borders = []

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int) -> None:
            visited[r][c] = True

            is_border = False

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    is_border = True
                elif grid[nr][nc] != original_color:
                    is_border = True
                elif not visited[nr][nc]:
                    dfs(nr, nc)

            if is_border:
                borders.append((r, c))

        dfs(row, col)

        for r, c in borders:
            grid[r][c] = color

        return grid

sol = Solution()

# Example 1
assert sol.colorBorder(
    [[1,1],[1,2]],
    0,
    0,
    3
) == [[3,3],[3,2]]

# Example 2
assert sol.colorBorder(
    [[1,2,2],[2,3,2]],
    0,
    1,
    3
) == [[1,3,3],[2,3,3]]

# Example 3
assert sol.colorBorder(
    [[1,1,1],[1,1,1],[1,1,1]],
    1,
    1,
    2
) == [[2,2,2],[2,1,2],[2,2,2]]

# Single cell grid
assert sol.colorBorder(
    [[5]],
    0,
    0,
    9
) == [[9]]

# Component already same color as target
assert sol.colorBorder(
    [[1,1],[1,1]],
    0,
    0,
    1
) == [[1,1],[1,1]]

# Interior cell should remain unchanged
assert sol.colorBorder(
    [[1,1,1],
     [1,1,1],
     [1,1,1]],
    1,
    1,
    5
) == [[5,5,5],
      [5,1,5],
      [5,5,5]]

# Irregular shaped component
assert sol.colorBorder(
    [[1,2,1],
     [1,1,1],
     [2,1,2]],
    1,
    1,
    7
) == [[7,2,7],
      [7,7,7],
      [2,7,2]]

Test Summary

Test Why
Example 1 Basic connected component
Example 2 Component touching multiple boundaries
Example 3 Large component with interior cell
Single cell grid Smallest possible input
Same target color Ensures traversal still works
Interior preservation Confirms non-border cells remain unchanged
Irregular shape Tests complex border detection

Edge Cases

Single Cell Component

A component containing only one cell can easily be mishandled if the algorithm assumes every cell has same-colored neighbors. In reality, a single isolated cell is always a border because it either touches the grid edge or neighboring cells of different colors.

The implementation handles this naturally because any missing or different neighbor sets is_border = True.

Entire Grid Is One Component

When every cell belongs to the same connected component, only the outer layer should be recolored. The interior cells must remain unchanged.

A buggy implementation might recolor all cells because they all belong to the component. Our border detection logic avoids this by requiring either an out-of-bounds neighbor or a different-colored neighbor before marking a cell as a border.

Recoloring During Traversal

One of the most common mistakes is recoloring cells immediately during DFS. If this happens, later neighbor checks may incorrectly think recolored cells belong to a different component.

This implementation avoids the issue by postponing recoloring until traversal is fully complete. The original grid values remain intact throughout DFS, ensuring accurate connectivity checks.