Coloring A Border solution and explanation
Google
9 more videos on this problem
Coloring a border || LeetcodePepcoding · 21:34 · 43K views
(Old) Leetcode 1034 - Depth First Search | Coloring Border | Connected Components of GraphNideesh Terapalli · 14:13 · 2K views
(Remade) Leetcode 1034 - Depth First Search | Coloring Border | Connected Components of GraphNideesh Terapalli · 8:48 · 2K views
Coloring A Border Medium | Module : Graph | In English | Java | Video_1Pepcoding · 17:30 · 1K views
Coloring A Border Medium | Module : Graph | In English | CPP | Video_1Pepcoding · 17:28 · 713 views
leetCode 1034 - Coloring A Border | JSer - algorithm & JavaScriptJSer · 26:13 · 466 views
leetcode 1034. Coloring A Border - traversal: 2 formats: iterative and recursiveCode-Yao · 19:02 · 209 views
1034. Coloring A Border 边界染色 0296代码魔术师magiciendecode · 11:05 · 208 views
Coloring A Border, Medium, LeetCode 1034H William Polenz · 22:04 · 85 views
No Sound Leetcode 1034: Coloring a BorderExtremeProgrammer · 4:08 · 43 views
The problem
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 < n
Approach overview
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.
Approach 1: Depth-First Search (DFS) Approach
This approach uses a depth-first search (DFS) to explore the grid and find the connected component starting from the given cell. We'll use DFS to identify all cells belonging to the same color as the starting cell. As we perform DFS, we mark cells that are potential borders if they are on the edge of the grid or adjacent to a different color. Finally, we change the color of these border cells to the specified new color.
def colorBorder(grid, row, col, color):
m, n = len(grid), len(grid[0])
original_color = grid[row][col]
border_cells = []
visited = [[False] * n for _ in range(m)]
def dfs(x, y):
if visited[x][y]:
return
visited[x][y] = True
is_border = False
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == original_color:
if not visited[nx][ny]:
dfs(nx, ny)
else:
is_border = True
else:
is_border = True
if is_border:
border_cells.append((x, y))
dfs(row, col)
for x, y in border_cells:
grid[x][y] = color
return gridclass Solution {
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int m = grid.length, n = grid[0].length;
int originalColor = grid[row][col];
boolean[][] visited = new boolean[m][n];
List<int[]> borders = new ArrayList<>();
dfs(grid, row, col, visited, borders, originalColor);
for (int[] cell : borders) {
grid[cell[0]][cell[1]] = color;
}
return grid;
}
private void dfs(int[][] grid, int x, int y, boolean[][] visited, List<int[]> borders, int originalColor) {
visited[x][y] = true;
int m = grid.length, n = grid[0].length;
boolean isBorder = false;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == originalColor) {
if (!visited[nx][ny]) dfs(grid, nx, ny, visited, borders, originalColor);
} else {
isBorder = true;
}
} else {
isBorder = true;
}
}
if (isBorder) borders.add(new int[]{x, y});
}
}#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int m = grid.size(), n = grid[0].size();
int originalColor = grid[row][col];
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<pair<int, int>> borders;
dfs(grid, row, col, visited, borders, originalColor);
for (auto& cell : borders) {
grid[cell.first][cell.second] = color;
}
return grid;
}
private:
void dfs(vector<vector<int>>& grid, int x, int y, vector<vector<bool>>& visited, vector<pair<int, int>>& borders, int originalColor) {
visited[x][y] = true;
int m = grid.size(), n = grid[0].size();
bool isBorder = false;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto& dir : directions) {
int nx = x + dir.first, ny = y + dir.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == originalColor) {
if (!visited[nx][ny]) dfs(grid, nx, ny, visited, borders, originalColor);
} else {
isBorder = true;
}
} else {
isBorder = true;
}
}
if (isBorder) borders.emplace_back(x, y);
}
};function colorBorder(grid, row, col, color) {
let m = grid.length, n = grid[0].length;
let originalColor = grid[row][col];
let visited = Array.from({ length: m }, () => Array(n).fill(false));
let borders = [];
function dfs(x, y) {
visited[x][y] = true;
let isBorder = false;
let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (let [dx, dy] of directions) {
let nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == originalColor) {
if (!visited[nx][ny]) dfs(nx, ny);
} else {
isBorder = true;
}
} else {
isBorder = true;
}
}
if (isBorder) borders.push([x, y]);
}
dfs(row, col);
for (let [x, y] of borders) {
grid[x][y] = color;
}
return grid;
}#include <stdbool.h>
#include <stdlib.h>
void dfs(int** grid, int m, int n, int x, int y, bool** visited, int originalColor, int** borders, int* borderSize) {
visited[x][y] = true;
bool isBorder = false;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < 4; i++) {
int nx = x + directions[i][0], ny = y + directions[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == originalColor) {
if (!visited[nx][ny]) dfs(grid, m, n, nx, ny, visited, originalColor, borders, borderSize);
} else {
isBorder = true;
}
} else {
isBorder = true;
}
}
if (isBorder) {
borders[*borderSize][0] = x;
borders[*borderSize][1] = y;
(*borderSize)++;
}
}
int** colorBorder(int** grid, int gridSize, int* gridColSize, int row, int col, int color, int* returnSize, int** returnColumnSizes) {
int m = gridSize, n = *gridColSize;
int originalColor = grid[row][col];
bool** visited = (bool**)malloc(m * sizeof(bool*));
for (int i = 0; i < m; i++) {
visited[i] = (bool*)calloc(n, sizeof(bool));
}
int** borders = (int**)malloc(m * n * sizeof(int*));
for (int i = 0; i < m * n; i++) {
borders[i] = (int*)malloc(2 * sizeof(int));
}
int borderSize = 0;
dfs(grid, m, n, row, col, visited, originalColor, borders, &borderSize);
for (int i = 0; i < borderSize; i++) {
grid[borders[i][0]][borders[i][1]] = color;
}
*returnSize = gridSize;
*returnColumnSizes = (int*)malloc(m * sizeof(int));
for (int i = 0; i < m; i++) {
(*returnColumnSizes)[i] = n;
}
for (int i = 0; i < m; i++) free(visited[i]);
free(visited);
for (int i = 0; i < m * n; i++) free(borders[i]);
free(borders);
return grid;
}We start by initializing a matrix to keep track of visited cells and a list to store border cells. Using a DFS function, we recursively visit each cell in the connected component. We mark a cell as a border if it is adjacent to a cell of a different color or is at the grid's edge. After identifying all border cells, we change their color to the new color.
Time Complexity: O(M*N) where M and N are the dimensions of the grid, because we potentially visit all cells.
Space Complexity: O(M*N) for the visited matrix and border cells list for storing the recursive call stack.
Approach 2: Breadth-First Search (BFS) Approach
This approach employs a breadth-first search (BFS) to explore the grid starting from the specified cell. BFS is helpful because it processes nodes at the current 'depth' level fully before moving on to the nodes at the next depth level, making it easy to track border cells by checking neighbors first.
from collections import deque
def colorBorder(grid, row, col, color):
original_color = grid[row][col]
m, n = len(grid), len(grid[0])
queue = deque([(row, col)])
visited = set([(row, col)])
borders = []
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
x, y = queue.popleft()
is_border = False
for dx, dy in directions:
nx, ny = x + dx, y + dy
if not (0 <= nx < m and 0 <= ny < n):
is_border = True
elif grid[nx][ny] != original_color:
is_border = True
elif (nx, ny) not in visited:
visited.add((nx, ny))
queue.append((nx, ny))
if is_border:
borders.append((x, y))
for x, y in borders:
grid[x][y] = color
return gridimport java.util.*;
class Solution {
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int m = grid.length, n = grid[0].length;
int originalColor = grid[row][col];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{row, col});
boolean[][] visited = new boolean[m][n];
visited[row][col] = true;
List<int[]> borders = new ArrayList<>();
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
boolean isBorder = false;
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != originalColor) {
isBorder = true;
} else if (!visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
if (isBorder) borders.add(new int[]{x, y});
}
for (int[] border : borders) {
grid[border[0]][border[1]] = color;
}
return grid;
}
}#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int m = grid.size(), n = grid[0].size();
int originalColor = grid[row][col];
queue<pair<int, int>> q;
q.push({row, col});
vector<vector<bool>> visited(m, vector<bool>(n, false));
visited[row][col] = true;
vector<pair<int, int>> borders;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
bool isBorder = false;
for (const auto& [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != originalColor) {
isBorder = true;
} else if (!visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
if (isBorder) borders.push_back({x, y});
}
for (const auto& border : borders) {
grid[border.first][border.second] = color;
}
return grid;
}
};function colorBorder(grid, row, col, color) {
let m = grid.length, n = grid[0].length;
let originalColor = grid[row][col];
let visited = Array.from({ length: m }, () => Array(n).fill(false));
let borders = [];
let queue = [[row, col]];
visited[row][col] = true;
let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
while (queue.length) {
let [x, y] = queue.shift();
let isBorder = false;
for (let [dx, dy] of directions) {
let nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] !== originalColor) {
isBorder = true;
} else if (!visited[nx][ny]) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
if (isBorder) {
borders.push([x, y]);
}
}
for (let [x, y] of borders) {
grid[x][y] = color;
}
return grid;
}using System;
using System.Collections.Generic;
public class Solution
{
public int[][] ColorBorder(int[][] grid, int row, int col, int color)
{
int m = grid.Length, n = grid[0].Length;
int originalColor = grid[row][col];
var directions = new[] { new[] { -1, 0 }, new[] { 1, 0 }, new[] { 0, -1 }, new[] { 0, 1 } };
var queue = new Queue<(int, int)>();
queue.Enqueue((row, col));
bool[,] visited = new bool[m, n];
visited[row, col] = true;
var borders = new List<(int, int)>();
while (queue.Count > 0)
{
var (x, y) = queue.Dequeue();
bool isBorder = false;
foreach (var dir in directions)
{
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != originalColor)
{
isBorder = true;
}
else if (!visited[nx, ny])
{
visited[nx, ny] = true;
queue.Enqueue((nx, ny));
}
}
if (isBorder) borders.Add((x, y));
}
foreach (var (x, y) in borders)
{
grid[x][y] = color;
}
return grid;
}
}In this solution, we use a queue to perform BFS, starting from the given cell. As we process each cell, we determine if it is a border by checking adjacent cells. If it's a border, it's added to the 'borders' list. Finally, we change the color of all border cells to the specified color.
Time Complexity: O(M*N), processing each grid cell.
Space Complexity: O(M*N) using the queue and storing borders.
Approach 3: Default Approach
function colorBorder(grid: number[][], row: number, col: number, color: number): number[][] {
const m = grid.length;
const n = grid[0].length;
const vis = new Array(m).fill(0).map(() => new Array(n).fill(false));
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number, c: number) => {
vis[i][j] = true;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (!vis[x][y]) {
if (grid[x][y] == c) {
dfs(x, y, c);
} else {
grid[i][j] = color;
}
}
} else {
grid[i][j] = color;
}
}
};
dfs(row, col, grid[row][col]);
return grid;
}func colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(int, int, int)
dfs = func(i, j, c int) {
vis[i][j] = true
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n {
if !vis[x][y] {
if grid[x][y] == c {
dfs(x, y, c)
} else {
grid[i][j] = color
}
}
} else {
grid[i][j] = color
}
}
}
dfs(row, col, grid[row][col])
return grid
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(M*N) where M and N are the dimensions of the grid, because we potentially visit all cells. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(M*N), processing each grid cell. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
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.