Solution: Coloring A Border

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Coloring A Border

Table of Contents

Contents are not accessible

Problem Statement

You are given an m x n integers grid, and three integers row, col, and color. Each cell in the grid has a color value represented by an integer.

Two cells are adjacent if they share a side. Cells with the same color and connected through adjacent cells form a connected component.

Color the border of the connected component that includes the cell at grid[row][col] with the new color provided. The border of a connected component consists of cells that are either adjacent to a cell with a different color or lie on the boundary of the grid.

Return the modified grid after coloring the border.

Examples

Example 1:

Input: row = 1, col = 1, color = 3, grid =

[[1, 2, 2], 
 [2, 2, 2], 
 [1, 2, 1]]

Expected Output: [[1, 3, 3], [3, 2, 3], [1, 3, 1]]

Justification: The connected component is the center block of 2s. The border cells of this block are colored with 3.

Example 2:

Input: row = 2, col = 0, color = 1, grid =

[[2, 2, 2], 
 [2, 2, 2], 
 [2, 2, 2]]

Expected Output: [[1, 1, 1], [1, 2, 1], [1, 1, 1]]

Justification: The connected component includes all cells. The border cells are colored with 1.

Example 3:

Input: row = 1, col = 2, color = 4, grid =

[[1, 1, 1, 1], 
 [1, 1, 2, 2], 
 [1, 1, 2, 2]]

Expected Output: [[1, 1, 1, 1], [1, 1, 4, 4], [1, 1, 4, 4]]

Justification: The connected component is the block of 2s. The border cells of this block are colored with 4.

Constraints:

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

Solution

To solve this problem, we need to identify the connected component that includes the specified cell and determine its border cells. The Depth-First Search (DFS) algorithm is effective for this task as it allows us to explore all cells in the connected component recursively. We can mark cells as part of the border if they are adjacent to cells with a different color or if they lie on the grid's boundary. Once we identify the border cells, we can change their color to the specified new color.

Step-by-Step Algorithm

Initialize variables:
- Store the number of rows and columns of the grid.
- Create a matrix to keep track of visited cells.
- Create a list to store border cells.
Get the original colo of the starting cell at (row, col).
Perform Depth-First Search (DFS) to explore the connected component:
- Mark the current cell as visited.
- Check if the current cell is a border cell:
  - Iterate over the four possible directions (right, down, left, up).
  - For each direction, calculate the new cell coordinates.
  - If the new cell is out of bounds or has a different color, mark the current cell as a border cell.
  - If the new cell is within bounds and has the same color and is unvisited, recursively perform DFS on the new cell.
- Add the current cell to the border list if it is a border cell.
Color the border cells with the new color.
Return the modified grid.

Algorithm Walkthrough

Given the grid:

grid = [[1, 2, 2], 
        [2, 2, 2], 
        [1, 2, 1]], 
row = 1, 
col = 1, 
color = 3

Initialize variables:
- rows = 3, cols = 3.
- visited = [[False, False, False], [False, False, False], [False, False, False]].
- borders = [].
Get the original color: originalColor = grid[1][1] = 2.
Perform DFS starting from (1, 1):
- Mark (1, 1) as visited: visited[1][1] = True.
- Initialize isBorder = False.
DFS on (1, 1):
- Direction (0, 1) (right):
  - New coordinates: (1, 2).
  - (1, 2) is within bounds and has the same color and is unvisited.
  - Continue DFS on (1, 2).
    
    DFS on (1, 2):
    - Mark (1, 2) as visited: visited[1][2] = True.
    - Initialize isBorder = False.
    - Direction (0, 1) (right):
      - New coordinates: (1, 3).
      - (1, 3) is out of bounds.
      - Mark (1, 2) as a border cell: isBorder = True.
    - Direction (1, 0) (down):
      - New coordinates: (2, 2).
      - (2, 2) is within bounds and has a different color.
      - Mark (1, 2) as a border cell: isBorder = True.
    - Direction (0, -1) (left):
      - New coordinates: (1, 1).
      - (1, 1) is within bounds and visited.
    - Direction (-1, 0) (up):
      - New coordinates: (0, 2).
      - (0, 2) is within bounds and has the same color and is unvisited.
      - Continue DFS on (0, 2).
    - Add (1, 2) to borders: borders = [(1, 2)].
    DFS on (0, 2):
    - Mark (0, 2) as visited: visited[0][2] = True.
    - Initialize isBorder = False.
    - Direction (0, 1) (right):
      - New coordinates: (0, 3).
      - (0, 3) is out of bounds.
      - Mark (0, 2) as a border cell: isBorder = True.
    - Direction (1, 0) (down):
      - New coordinates: (1, 2).
      - (1, 2) is within bounds and visited.
    - Direction (0, -1) (left):
      - New coordinates: (0, 1).
      - (0, 1) is within bounds and has the same color and is unvisited.
      - Continue DFS on (0, 2).
    - Direction (-1, 0) (up):
      - New coordinates: (-1, 2).
      - (-1, 2) is out of bounds.
      - Mark (0, 2) as a border cell: isBorder = True.
    - Add (0, 2) to borders: borders = [(1, 2), (0, 2)].
    DFS on (0, 1):
    - Mark (0, 1) as visited: visited[0][1] = True.
    - Initialize isBorder = False.
    - Direction (0, 1) (right):
      - New coordinates: (0, 2).
      - (0, 2) is within bounds and visited.
    - Direction (1, 0) (down):
      - New coordinates: (1, 1).
      - (1, 1) is within bounds and visited.
    - Direction (0, -1) (left):
      - New coordinates: (0, 0).
      - (0, 0) is within bounds and has a different color.
      - Mark (0, 1) as a border cell: isBorder = True.
    - Direction (-1, 0) (up):
      - New coordinates: (-1, 1).
      - (-1, 1) is out of bounds.
      - Mark (0, 1) as a border cell: isBorder = True.
    - Add (0, 1) to borders: borders = [(1, 2), (0, 2), (0, 1)].
- Direction (1, 0) (down):
- New coordinates: (2, 1).
- (2, 1) is within bounds and has the same color and is unvisited.
- Continue DFS on (2, 1).
  
  DFS on (2, 1):
  - Mark (2, 1) as visited: visited[2][1] = True.
  - Initialize isBorder = False.
  - Direction (0, 1) (right):
    - New coordinates: (2, 2).
    - (2, 2) is within bounds and has a different color.
    - Mark (2, 1) as a border cell: isBorder = True.
  - Direction (1, 0) (down):
    - New coordinates: (3, 1).
    - (3, 1) is out of bounds.
    - Mark (2, 1) as a border cell: isBorder = True.
  - Direction (0, -1) (left):
    - New coordinates: (2, 0).
    - (2, 0) is within bounds and has a different color.
    - Mark (2, 1) as a border cell: isBorder = True.
  - Direction (-1, 0) (up):
    - New coordinates: (1, 1).
    - (1, 1) is within bounds and visited.
  - Add (2, 1) to borders: borders = [(1, 2), (0, 2), (2, 1), (0, 1)].
- Direction (0, -1) (left):
  - New coordinates: (1, 0).
  - (1, 0) is within bounds and has the same color and is unvisited.
  - Continue DFS on (1, 0).
    
    DFS on (1, 0):
    - Mark (1, 0) as visited: visited[1][0] = True.
    - Initialize isBorder = False.
    - Direction (0, 1) (right):
      - New coordinates: (1, 1).
      - (1, 1) is within bounds and visited.
    - Direction (1, 0) (down):
      - New coordinates: (2, 0).
      - (2, 0) is within bounds and has a different color.
      - Mark (1, 0) as a border cell: isBorder = True.
    - Direction (0, -1) (left):
      - New coordinates: (1, -1).
      - (1, -1) is out of bounds.
      - Mark (1, 0) as a border cell: isBorder = True.
    - Direction (-1, 0) (up):
      - New coordinates: (0, 0).
      - (0, 0) is within bounds and has a different color.
      - Mark (1, 0) as a border cell: isBorder = True.
    - Add (1, 0) to borders: borders = [(1, 2), (0, 2), (2, 1), (1, 0), (0, 1)].
- Direction (-1, 0) (up):
  - New coordinates: (0, 1).
  - (0, 1) is already visited.
Color the border cells:
- Change color of (1, 2) to 3.
- Change color of (0, 2) to 3.
- Change color of (2, 1) to 3.
- Change color of (1, 0) to 3.
- Change color of (0, 1) to 3.
Return the modified grid:

[[1, 3, 3],
 [3, 2, 3],
 [1, 3, 1]]

Code

Python3

. . . .

Complexity Analysis

Time Complexity: The time complexity of the algorithm is $O(m \times n)$ where (m) is the number of rows and (n) is the number of columns. This is because we potentially visit every cell in the grid once.
Space Complexity: The space complexity is $O(m \times n)$ due to the storage required for the visited array and the recursion stack in the worst case. The border list also takes up to $O(m \times n)$ space.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible