Repaint a Connected Patch of Tiles
Solve this ProblemYou are given a grid of tile colours and a starting tile. Repaint the starting tile and every tile connected to it through same-coloured tiles (moving up, down, left or right) with a new colour, and return the grid.
The trap: when the new colour equals the old one, no work is needed. A search that recognises unpainted tiles by their colour would otherwise keep revisiting tiles.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; 0 ≤ image[r][c], color ≤ 99 - ◆
0 ≤ sr < rows and 0 ≤ sc < cols give the starting tile - ◆
A patch is every tile reachable from the start by moving up, down, left or right through tiles of the same colour as the start - ◆
Repaint the whole patch with color and return the new grid (the input grid must not be needed afterwards)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Grow the Marked Patch by Rescanning the Grid
BruteMark the start tile. Then keep scanning the whole grid: any unmarked tile that has the original colour and touches a marked tile becomes marked. Repeat until a full scan marks nothing new, and finally paint every marked tile. A patch grows by at least one tile per scan, so a snake-shaped patch needs up to R·C scans of R·C tiles each: O((R·C)²).
O((R·C)²)O(R·C)1class Solution {
2 public int[][] paintRegion(int[][] image, int sr, int sc, int color) {
3 int rows = image.length, cols = image[0].length;
4 int original = image[sr][sc];
5 int[][] result = new int[rows][cols];
6 for (int r = 0; r < rows; r++) result[r] = image[r].clone();
7 if (original == color) return result;
8 boolean[][] marked = new boolean[rows][cols];
9 marked[sr][sc] = true;
10 boolean changed = true;
11 while (changed) {
12 changed = false;
13 for (int r = 0; r < rows; r++) {
14 for (int c = 0; c < cols; c++) {
15 if (marked[r][c] || image[r][c] != original) continue;
16 boolean touches = (r > 0 && marked[r - 1][c]) || (r < rows - 1 && marked[r + 1][c])
17 || (c > 0 && marked[r][c - 1]) || (c < cols - 1 && marked[r][c + 1]);
18 if (touches) {
19 marked[r][c] = true;
20 changed = true;
21 }
22 }
23 }
24 }
25 for (int r = 0; r < rows; r++) {
26 for (int c = 0; c < cols; c++) {
27 if (marked[r][c]) result[r][c] = color;
28 }
29 }
30 return result;
31 }
32}Optimal — Breadth-First Flood From the Start Tile
OptimalRemember the start tile's colour. If it already equals the new colour, return a copy unchanged (otherwise the search would never stop recognising tiles as unpainted). Otherwise paint the start tile, put it in a queue, and repeatedly take a tile and look at its four neighbours: any neighbour that still has the original colour is painted immediately and queued. Painting on discovery doubles as the visited mark, so each tile is handled once: O(R·C).
O(R·C)O(R·C)1class Solution {
2 public int[][] paintRegion(int[][] image, int sr, int sc, int color) {
3 int rows = image.length, cols = image[0].length;
4 int original = image[sr][sc];
5 int[][] result = new int[rows][cols];
6 for (int r = 0; r < rows; r++) result[r] = image[r].clone();
7 if (original == color) return result;
8 int[] dr = {1, -1, 0, 0};
9 int[] dc = {0, 0, 1, -1};
10 Deque<int[]> queue = new ArrayDeque<>();
11 result[sr][sc] = color;
12 queue.add(new int[]{sr, sc});
13 while (!queue.isEmpty()) {
14 int[] cell = queue.poll();
15 for (int d = 0; d < 4; d++) {
16 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
17 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && result[nr][nc] == original) {
18 result[nr][nc] = color;
19 queue.add(new int[]{nr, nc});
20 }
21 }
22 }
23 return result;
24 }
25}