Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 < nProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[1,1],[1,2]] 0 0 3
[[1,2,2],[2,3,2]] 0 1 3
[[1,1,1],[1,1,1],[1,1,1]] 1 1 2
island-perimeter)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1034: Coloring A Border
class Solution {
private int[][] grid;
private int color;
private int m;
private int n;
private boolean[][] vis;
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
this.grid = grid;
this.color = color;
m = grid.length;
n = grid[0].length;
vis = new boolean[m][n];
dfs(row, col, grid[row][col]);
return grid;
}
private void dfs(int i, int j, int c) {
vis[i][j] = true;
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], 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;
}
}
}
}
// Accepted solution for LeetCode #1034: Coloring A Border
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
}
# Accepted solution for LeetCode #1034: Coloring A Border
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
// Accepted solution for LeetCode #1034: Coloring A Border
struct Solution;
impl Solution {
fn color_border(mut grid: Vec<Vec<i32>>, r0: i32, c0: i32, color: i32) -> Vec<Vec<i32>> {
let n = grid.len();
let m = grid[0].len();
let r0 = r0 as usize;
let c0 = c0 as usize;
let c_color = grid[r0][c0];
let b_color = color;
let mut visited: Vec<Vec<bool>> = vec![vec![false; m]; n];
Self::dfs(r0, c0, &mut visited, &mut grid, b_color, c_color, n, m);
grid
}
fn dfs(
i: usize,
j: usize,
visited: &mut [Vec<bool>],
grid: &mut [Vec<i32>],
b_color: i32,
c_color: i32,
n: usize,
m: usize,
) {
visited[i][j] = true;
let top = if i == 0 {
true
} else {
if grid[i - 1][j] != c_color {
!visited[i - 1][j]
} else {
if !visited[i - 1][j] {
Self::dfs(i - 1, j, visited, grid, b_color, c_color, n, m);
}
false
}
};
let left = if j == 0 {
true
} else {
if grid[i][j - 1] != c_color {
!visited[i][j - 1]
} else {
if !visited[i][j - 1] {
Self::dfs(i, j - 1, visited, grid, b_color, c_color, n, m);
}
false
}
};
let down = if i + 1 == n {
true
} else {
if grid[i + 1][j] != c_color {
!visited[i + 1][j]
} else {
if !visited[i + 1][j] {
Self::dfs(i + 1, j, visited, grid, b_color, c_color, n, m);
}
false
}
};
let right = if j + 1 == m {
true
} else {
if grid[i][j + 1] != c_color {
!visited[i][j + 1]
} else {
if !visited[i][j + 1] {
Self::dfs(i, j + 1, visited, grid, b_color, c_color, n, m);
}
false
}
};
if top || left || down || right {
grid[i][j] = b_color;
}
}
}
#[test]
fn test() {
let grid = vec_vec_i32![[1, 1], [1, 2]];
let r0 = 0;
let c0 = 0;
let color = 3;
let res = vec_vec_i32![[3, 3], [3, 2]];
assert_eq!(Solution::color_border(grid, r0, c0, color), res);
let grid = vec_vec_i32![[1, 2, 2], [2, 3, 2]];
let r0 = 0;
let c0 = 1;
let color = 3;
let res = vec_vec_i32![[1, 3, 3], [2, 3, 3]];
assert_eq!(Solution::color_border(grid, r0, c0, color), res);
let grid = vec_vec_i32![[1, 1, 1], [1, 1, 1], [1, 1, 1]];
let r0 = 1;
let c0 = 1;
let color = 2;
let res = vec_vec_i32![[2, 2, 2], [2, 1, 2], [2, 2, 2]];
assert_eq!(Solution::color_border(grid, r0, c0, color), res);
}
// Accepted solution for LeetCode #1034: Coloring A Border
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.