Ctrl K

Outline a Color Patch

Medium
A picture is given as a rectangular table canvas: the number in each cell is its color. Two cells are neighbours when they share a side (diagonal cells are not neighbours). A **patch** is a maximal connected group of neighbouring cells of the same color. A patch cell lies on the patch **outline** if it sits on the edge of the canvas (first or last row or column), or if at least one of its neighbours is not part of the patch. Take the patch that contains canvas[r][c] and repaint every cell of its outline with color paint. All other cells, including the inner cells of the patch, stay the same. Return the resulting table. Note that membership in the patch is decided by the original colors, not by cells you have already repainted.
Example 1
canvas=[[4, 4, 1], [4, 4, 1], [2, 4, 4]], r=0, c=0, paint=9 → [[9, 9, 1], [9, 9, 1], [2, 9, 9]]

The patch of color 4 that contains (0, 0) has six cells. Each of them either sits on the edge of the canvas or touches a cell of another color, so all six get repainted.

Example 2
canvas=[[5, 5, 5, 5], [5, 5, 5, 5], [5, 5, 5, 5]], r=1, c=2, paint=7 → [[7, 7, 7, 7], [7, 5, 5, 7], [7, 7, 7, 7]]

The whole canvas is one patch. The inner cells (1, 1) and (1, 2) are surrounded by their own color and stay as they are; every other cell lies on the canvas edge.

Example 3
canvas=[[3, 6], [6, 3]], r=0, c=1, paint=6 → [[3, 6], [6, 3]]

The patch is a single cell, since diagonal cells are not neighbours. It is repainted with the same color 6, so the canvas does not change.

Constraints
  • 1 ≤ number of rows, number of columns of canvas ≤ 50
  • All rows have the same length
  • 1 ≤ canvas[i][j] ≤ 1000
  • 1 ≤ paint ≤ 1000
  • 0 ≤ r < number of rows, 0 ≤ c < number of columns
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsDrain the Landlocked Ponds MediumLand Regions on a Map MediumRain Reaching Both Seas MediumCan the Ball Stop at the Target MediumShortest Path of a Rolling Ball Medium
loading Python…
Input
canvas=[[4, 4, 1], [4, 4, 1], [2, 4, 4]], r=0, c=0, paint=9
Expected
[[9, 9, 1], [9, 9, 1], [2, 9, 9]]

Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.