Coloring A Border

Medium
1691.

Coloring A Border

Coloring A Border is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon interviews.

You are given an m x n integer matrix grid, where each value is the colour of that cell, and three integers row, col and color.

Two cells are adjacent if they share a side. Two cells belong to the same connected component if they have the same colour and are linked by a chain of adjacent same-coloured cells.

The border of a component is every cell of it that is either adjacent to a cell outside the component or lies on the edge of the grid.

Recolour the border of the component containing grid[row][col] with color, and return the resulting 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]]
Explanation
The centre cell is surrounded by its own component and is not on the grid's edge, so it keeps its colour.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j], color <= 1000
  • 0 <= row < m
  • 0 <= col < n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number} row
 * @param {number} col
 * @param {number} color
 * @return {number[][]}
 */
var colorBorder = function(grid, row, col, color) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Coloring A Border — Solution in Python, Java & C++

Coloring A Border solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Coloring A Border is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon interviews.

Problem statement

You are given an m x n integer matrix grid, where each value is the colour of that cell, and three integers row, col and color.

Two cells are adjacent if they share a side. Two cells belong to the same connected component if they have the same colour and are linked by a chain of adjacent same-coloured cells.

The border of a component is every cell of it that is either adjacent to a cell outside the component or lies on the edge of the grid.

Recolour the border of the component containing grid[row][col] with color, and return the resulting 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]]
Explanation: The centre cell is surrounded by its own component and is not on the grid's edge, so it keeps its colour.

Constraints

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

Hints for Coloring A Border

  1. Hint 1

    First find the whole component with a DFS or BFS from (row, col), moving only to cells of the starting colour.

  2. Hint 2

    A component cell is on the border if it is on the grid's edge or any of its four neighbours is not in the component.

  3. Hint 3

    Decide every border cell against the original colours, then paint — painting during the search changes the answers for cells you have not checked yet.

How to solve Coloring A Border

Separate finding from painting: mark the component, decide which marked cells are on its border using the marks, then recolour those cells.

Approach

  1. Let c0 = grid[row][col]. Flood-fill from (row, col) over cells equal to c0, marking them as in the component.
  2. For each marked cell, it is a border cell if it lies on the outer edge of the grid or has a neighbour that is not marked.
  3. Set every border cell to color and return the grid.

Why it works

Being on the border depends only on membership in the component, which the marks record exactly. Because no cell is repainted until every border test is done, a recoloured neighbour can never be mistaken for a foreign cell — even when color equals c0.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Recolouring during the DFS makes interior cells look like they touch another colour.
  • Cells of the same colour that are not connected to the start are a different component and must not change.
  • A one-row or one-column component is entirely border.

Reference solution

Python

from typing import List

def colorBorder(grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    c0 = grid[row][col]
    inside = [[False] * n for _ in range(m)]
    inside[row][col] = True
    stack = [(row, col)]
    cells = []
    while stack:
        r, c = stack.pop()
        cells.append((r, c))
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < m and 0 <= nc < n and not inside[nr][nc] and grid[nr][nc] == c0:
                inside[nr][nc] = True
                stack.append((nr, nc))
    border = []
    for r, c in cells:
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if not (0 <= nr < m and 0 <= nc < n) or not inside[nr][nc]:
                border.append((r, c))
                break
    out = [row_[:] for row_ in grid]
    for r, c in border:
        out[r][c] = color
    return out

Java

public static int[][] colorBorder(int[][] grid, int row, int col, int color) {
    int m = grid.length, n = grid[0].length, c0 = grid[row][col];
    boolean[][] inside = new boolean[m][n];
    int[][] out = new int[m][];
    for (int i = 0; i < m; i++) out[i] = grid[i].clone();
    int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
    int[] cells = new int[m * n];
    int cnt = 0;
    inside[row][col] = true;
    cells[cnt++] = row * n + col;
    for (int h = 0; h < cnt; h++) {
        int r = cells[h] / n, c = cells[h] % n;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nc >= 0 && nr < m && nc < n && !inside[nr][nc] && grid[nr][nc] == c0) {
                inside[nr][nc] = true;
                cells[cnt++] = nr * n + nc;
            }
        }
    }
    for (int h = 0; h < cnt; h++) {
        int r = cells[h] / n, c = cells[h] % n;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || !inside[nr][nc]) { out[r][c] = color; break; }
        }
    }
    return out;
}

C++

vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
    int m = grid.size(), n = grid[0].size(), c0 = grid[row][col];
    vector<vector<bool>> inside(m, vector<bool>(n, false));
    vector<vector<int>> out = grid;
    int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    vector<pair<int, int>> cells{{row, col}};
    inside[row][col] = true;
    for (size_t h = 0; h < cells.size(); h++) {
        int r = cells[h].first, c = cells[h].second;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nc >= 0 && nr < m && nc < n && !inside[nr][nc] && grid[nr][nc] == c0) {
                inside[nr][nc] = true;
                cells.push_back({nr, nc});
            }
        }
    }
    for (auto& cell : cells) {
        int r = cell.first, c = cell.second;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || !inside[nr][nc]) { out[r][c] = color; break; }
        }
    }
    return out;
}

JavaScript

var colorBorder = function(grid, row, col, color) {
    var m = grid.length, n = grid[0].length, c0 = grid[row][col];
    var inside = [], out = [];
    for (var i = 0; i < m; i++) {
        inside.push(new Array(n).fill(false));
        out.push(grid[i].slice());
    }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    inside[row][col] = true;
    var cells = [[row, col]];
    for (var h = 0; h < cells.length; h++) {
        for (var k = 0; k < 4; k++) {
            var nr = cells[h][0] + dr[k], nc = cells[h][1] + dc[k];
            if (nr >= 0 && nc >= 0 && nr < m && nc < n && !inside[nr][nc] && grid[nr][nc] === c0) {
                inside[nr][nc] = true;
                cells.push([nr, nc]);
            }
        }
    }
    for (var j = 0; j < cells.length; j++) {
        var r = cells[j][0], c = cells[j][1];
        for (var d = 0; d < 4; d++) {
            var ar = r + dr[d], ac = c + dc[d];
            if (ar < 0 || ac < 0 || ar >= m || ac >= n || !inside[ar][ac]) { out[r][c] = color; break; }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)