Coloring A Border — Solution in Python, Java & C++
Coloring A Border solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.
Coloring A Border is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n integer matrix grid, where each value is the colour of that cell, and three integers row, col and color.
Two cells are adjacent if they share a side. Two cells belong to the same connected component if they have the same colour and are linked by a chain of adjacent same-coloured cells.
The border of a component is every cell of it that is either adjacent to a cell outside the component or lies on the edge of the grid.
Recolour the border of the component containing grid[row][col] with color, and return the resulting 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]]
Explanation: The centre cell is surrounded by its own component and is not on the grid's edge, so it keeps its colour.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j], color <= 10000 <= row < m0 <= col < n
Hints for Coloring A Border
Hint 1
First find the whole component with a DFS or BFS from
(row, col), moving only to cells of the starting colour.Hint 2
A component cell is on the border if it is on the grid's edge or any of its four neighbours is not in the component.
Hint 3
Decide every border cell against the original colours, then paint — painting during the search changes the answers for cells you have not checked yet.
How to solve Coloring A Border
Separate finding from painting: mark the component, decide which marked cells are on its border using the marks, then recolour those cells.
Approach
- Let
c0 = grid[row][col]. Flood-fill from(row, col)over cells equal toc0, marking them as in the component. - For each marked cell, it is a border cell if it lies on the outer edge of the grid or has a neighbour that is not marked.
- Set every border cell to
colorand return the grid.
Why it works
Being on the border depends only on membership in the component, which the marks record exactly. Because no cell is repainted until every border test is done, a recoloured neighbour can never be mistaken for a foreign cell — even when color equals c0.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Recolouring during the DFS makes interior cells look like they touch another colour.
- Cells of the same colour that are not connected to the start are a different component and must not change.
- A one-row or one-column component is entirely border.
Reference solution
Python
from typing import List
def colorBorder(grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
m, n = len(grid), len(grid[0])
c0 = grid[row][col]
inside = [[False] * n for _ in range(m)]
inside[row][col] = True
stack = [(row, col)]
cells = []
while stack:
r, c = stack.pop()
cells.append((r, c))
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and not inside[nr][nc] and grid[nr][nc] == c0:
inside[nr][nc] = True
stack.append((nr, nc))
border = []
for r, c in cells:
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if not (0 <= nr < m and 0 <= nc < n) or not inside[nr][nc]:
border.append((r, c))
break
out = [row_[:] for row_ in grid]
for r, c in border:
out[r][c] = color
return outJava
public static int[][] colorBorder(int[][] grid, int row, int col, int color) {
int m = grid.length, n = grid[0].length, c0 = grid[row][col];
boolean[][] inside = new boolean[m][n];
int[][] out = new int[m][];
for (int i = 0; i < m; i++) out[i] = grid[i].clone();
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int[] cells = new int[m * n];
int cnt = 0;
inside[row][col] = true;
cells[cnt++] = row * n + col;
for (int h = 0; h < cnt; h++) {
int r = cells[h] / n, c = cells[h] % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && !inside[nr][nc] && grid[nr][nc] == c0) {
inside[nr][nc] = true;
cells[cnt++] = nr * n + nc;
}
}
}
for (int h = 0; h < cnt; h++) {
int r = cells[h] / n, c = cells[h] % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || !inside[nr][nc]) { out[r][c] = color; break; }
}
}
return out;
}C++
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int m = grid.size(), n = grid[0].size(), c0 = grid[row][col];
vector<vector<bool>> inside(m, vector<bool>(n, false));
vector<vector<int>> out = grid;
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<pair<int, int>> cells{{row, col}};
inside[row][col] = true;
for (size_t h = 0; h < cells.size(); h++) {
int r = cells[h].first, c = cells[h].second;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && !inside[nr][nc] && grid[nr][nc] == c0) {
inside[nr][nc] = true;
cells.push_back({nr, nc});
}
}
}
for (auto& cell : cells) {
int r = cell.first, c = cell.second;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || !inside[nr][nc]) { out[r][c] = color; break; }
}
}
return out;
}JavaScript
var colorBorder = function(grid, row, col, color) {
var m = grid.length, n = grid[0].length, c0 = grid[row][col];
var inside = [], out = [];
for (var i = 0; i < m; i++) {
inside.push(new Array(n).fill(false));
out.push(grid[i].slice());
}
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
inside[row][col] = true;
var cells = [[row, col]];
for (var h = 0; h < cells.length; h++) {
for (var k = 0; k < 4; k++) {
var nr = cells[h][0] + dr[k], nc = cells[h][1] + dc[k];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && !inside[nr][nc] && grid[nr][nc] === c0) {
inside[nr][nc] = true;
cells.push([nr, nc]);
}
}
}
for (var j = 0; j < cells.length; j++) {
var r = cells[j][0], c = cells[j][1];
for (var d = 0; d < 4; d++) {
var ar = r + dr[d], ac = c + dc[d];
if (ar < 0 || ac < 0 || ar >= m || ac >= n || !inside[ar][ac]) { out[r][c] = color; break; }
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)