Is Coloring A Border easy or hard?

Coloring A Border is rated Medium on LeetCode. The challenge comes from correctly identifying border cells while traversing a connected component and ensuring that internal cells remain unchanged. Strong familiarity with BFS or DFS on matrices makes the problem straightforward.

Coloring A Border Python/Java solution

Python and Java implementations typically follow the same logic: run DFS or BFS from the starting cell, track visited cells, detect borders by checking neighbors, and recolor those border cells. The algorithm maintains O(m*n) time complexity and O(m*n) auxiliary space.

How to solve Coloring A Border in O(n)?

Treat the grid as a graph and perform a DFS or BFS from the starting cell. Track visited cells and check four-directional neighbors to determine if a cell is on the boundary of the component. Store border cells separately and recolor them after traversal. The algorithm processes each cell once, giving O(m*n) time complexity.

What is the best approach for Coloring A Border?

The optimal solution uses either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the connected component starting from the given cell. During traversal, each cell checks its four neighbors to determine whether it lies on the component boundary. Border cells are recolored after the traversal completes. Both approaches run in O(m*n) time.

Is Coloring A Border asked at Google/Amazon/Meta?

Grid traversal and connected component problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations involving BFS or DFS on matrices are common because they test graph fundamentals, boundary detection, and careful state tracking.

What data structure is used in Coloring A Border?

The solution primarily uses graph traversal structures. DFS implementations rely on recursion or an explicit stack, while BFS uses a queue. A visited matrix or marking technique is also required to avoid revisiting cells in the same connected component.

What is the time complexity of Coloring A Border?

The time complexity is O(m*n), where m and n are the grid dimensions. Each cell in the connected component is visited at most once, and every visit checks four neighbors. This keeps the work proportional to the total number of cells in the grid.

Description Hints 1 Solution Video 21:34

1034. Coloring A Border

Medium51.8% acceptance3 companies

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.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j], color <= 1000
0 <= row < m
0 <= col < n

Asked at 3 companies

Booking.com

Google Microsoft

Topics

Hints open one at a time

Hint 1

Use a DFS to find every square in the component. Then for each square, color it if it has a neighbor that is outside the grid or a different color.

21:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution