Recolor the Cross-Stitch
You are planning a cross-stitch picture on squared paper. Each square holds a thread number, like 3 for sky blue or 7 for grass green. Halfway through, you decide one patch of sky should be a sunset orange instead.
A patch is every square you can reach from the one you tap by stepping up, down, left or right onto the same thread number. Squares that only touch at a corner are not part of it, and neither is a separate patch of the same color elsewhere on the paper.
Your task
Write recolorPatch(pattern, row, col, newColor). pattern is a grid of thread numbers. Change every square in the patch that contains pattern[row][col] to newColor, and return the grid.
Two squares are in the same patch if you can walk from one to the other through squares of that same thread number, moving only up, down, left or right. You may change pattern in place or build a new grid. If newColor is already the patch's color, nothing changes.
recolorPatch(pattern: int[][], row: int, col: int, newColor: int) → int[][]
Examples
pattern = [[3, 3, 5], [3, 5, 5], [5, 3, 3]] row = 0 col = 0 newColor = 8
[[8, 8, 5], [8, 5, 5], [5, 3, 3]]
The tapped square holds 3. Its patch is the three 3s in the top-left corner. The two 3s in the bottom row also hold 3, but no up/down/left/right path of 3s joins them to the corner, so they stay 3.
pattern = [[1, 2], [2, 1]] row = 0 col = 0 newColor = 4
[[4, 2], [2, 1]]
The two 1s touch only at a corner, so they are separate patches. Only the top-left square changes.
Constraints
- 1 ≤ rows, cols ≤ 20
- 0 ≤ pattern[r][c], newColor ≤ 99
- 0 ≤ row < rows and 0 ≤ col < cols
Start with brute force
Recolor the tapped square, then sweep the whole grid again and again: any square with the old color that sits next to a recolored one gets recolored too. Stop when a full sweep changes nothing.
It works, but a patch shaped like a winding snake that doubles back against the sweep direction can grow by only a few squares per sweep. A 20 × 20 grid could need around a hundred sweeps of 400 squares each. A search that follows the patch directly touches each square once.
Hints
0 of 4 shown- Hint 1
In the first example, tap the top-left 3. Which squares change straight away, and which only change because a neighbor of theirs changed?
- Hint 2
Think of each square as a spot on a map, joined to the up to four squares next to it. The patch is everything you can reach from the start without stepping onto a different number.
- Hint 3
You need a way to visit every reachable square exactly once. Recursion on the four neighbors does it, and so does a stack or a queue. What stops you from visiting the same square forever?
- Hint 4
Remember the old color first. Visit a square only if it is inside the grid and still holds the old color; recolor it the moment you visit it, then visit its four neighbors. Recoloring doubles as the "already visited" mark, but only when the new color differs from the old one, so return early if they are equal.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The grid is a graph in disguise. Every square is a node, and it has an edge to each of its up-to-four neighbors that hold the same thread number. A patch is everything reachable from the tapped square, so the job is a plain graph search.
Trace the first example, [[3,3,5],[3,5,5],[5,3,3]], tapping (0,0) with new color 8. Old color is 3.
- Recolor (0,0) to 8 and push it. Stack: (0,0).
- Pop (0,0). Below it, (1,0) is 3: recolor and push. To the right, (0,1) is 3: recolor and push. Stack: (1,0), (0,1).
- Pop (0,1). Its neighbors are (1,1) = 5, (0,2) = 5 and (0,0), which is now 8. Nothing to add.
- Pop (1,0). Its neighbors are (2,0) = 5, (1,1) = 5 and (0,0) = 8. Nothing to add. The stack is empty.
Result: [[8,8,5],[8,5,5],[5,3,3]]. The 3s in the bottom row were never reached, because every path to them crosses a 5.
Recoloring a square as soon as you push it doubles as the visited mark: a recolored square no longer holds the old color, so it is never pushed twice. That trick breaks if the new color equals the old one, because then nothing ever looks visited and the search loops forever. The early return handles it.
function recolorPatch(pattern, row, col, newColor) {
const oldColor = pattern[row][col];
if (oldColor === newColor) return pattern; // nothing to do
const rows = pattern.length, cols = pattern[0].length;
const stack = [[row, col]];
pattern[row][col] = newColor;
while (stack.length > 0) {
const [r, c] = stack.pop();
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (pattern[nr][nc] !== oldColor) continue;
pattern[nr][nc] = newColor; // recolor = mark as visited
stack.push([nr, nc]);
}
}
return pattern;
}def recolor_patch(pattern, row, col, new_color):
old_color = pattern[row][col]
if old_color == new_color:
return pattern # nothing to do
rows, cols = len(pattern), len(pattern[0])
stack = [(row, col)]
pattern[row][col] = new_color
while stack:
r, c = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and pattern[nr][nc] == old_color:
pattern[nr][nc] = new_color # recolor = mark as visited
stack.append((nr, nc))
return patternRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.