Coloring A Border

MediumGraphsdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n integer matrix grid and a starting cell (row, col). Two cells are *adjacent* if they share an edge. The *component* of the starting cell is the set of cells with the same value that can be reached from it through adjacent cells of that value. A cell of the component is on its *border* if it lies on the outer edge of the grid, or if at least one adjacent cell is not in the component. Paint every border cell of the component with color and return the resulting grid. Whether a cell is on the border must be decided from the **original** grid, before any painting.

Examples

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]
The component is the three 1s; all of them touch the grid edge.
Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]
The component is the three connected 2s in the top-right; each is on the grid edge.
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]]
The center cell is surrounded by component cells and is not on the grid edge, so it keeps its color.

Constraints

  • `1 <= m, n <= 50`
  • `1 <= grid[i][j], color <= 1000`
  • `0 <= row < m`
  • `0 <= col < n`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems