Problem Description

You have an m x n matrix called grid where each cell contains an integer representing a color value. You're also given three parameters: row, col (coordinates of a starting cell), and color (a new color value to apply).

The problem involves understanding connected components and their borders:

• Adjacent squares: Two cells that share an edge (up, down, left, or right - not diagonals)
• Connected component: A group of cells that have the same color and are connected through adjacent cells
• Border of a connected component: Cells within the component that either:
  • Touch at least one cell with a different color, OR
  • Are on the edge of the grid (first/last row or column)

Your task is to:

1. Find the connected component that contains the cell at position grid[row][col]
2. Identify all border cells of this component
3. Change the color of these border cells to the given color
4. Return the modified grid

For example, if you have a region of cells with the same color, only the cells on the perimeter of that region (those touching different colors or the grid edge) should be recolored, while interior cells remain unchanged.

The solution uses DFS (Depth-First Search) to traverse the connected component starting from grid[row][col]. During traversal, it marks visited cells and checks each cell's neighbors. If a cell has a neighbor with a different color or is at the grid boundary, it's identified as a border cell and colored with the new color.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and edges connect adjacent cells (up, down, left, right). We need to traverse connected components based on color similarity.

Is it a tree?

• No: The grid structure is not a tree. It's a 2D grid where cells can form cycles when they have the same color, and there's no hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The grid connections are undirected (if cell A is adjacent to cell B, then B is also adjacent to A), and cycles can exist within same-colored regions.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between cells. We're identifying and modifying borders of a connected component.

Does the problem involve connectivity?

• Yes: The core of the problem is finding connected components - groups of cells with the same color that are connected through adjacent cells. We need to explore all cells connected to the starting cell.

Does the problem have small constraints?

• Yes: Grid problems typically have manageable constraints (m × n grid), allowing us to visit each cell and explore the connected component efficiently.

DFS/backtracking?

• Yes: DFS is perfect for exploring connected components. Starting from grid[row][col], we recursively visit all adjacent cells with the same color, marking borders as we go.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to traverse the connected component starting from the given cell, identify border cells during traversal, and color them accordingly.

Intuition

When we think about finding and coloring the border of a connected component, we need to first understand what makes a cell a "border cell". A cell is on the border if it's part of our connected component BUT either touches the edge of the grid or touches a cell with a different color.

The natural approach is to explore the entire connected component starting from grid[row][col]. As we visit each cell, we can check its surroundings to determine if it's a border cell. This exploration pattern naturally fits DFS because:

1. We need to visit all cells in the component exactly once
2. From each cell, we branch out to its neighbors with the same color
3. We need to track which cells we've already visited to avoid infinite loops

The key insight is that we can identify border cells during our DFS traversal. For each cell we visit, we check all four adjacent positions:

• If an adjacent position is out of bounds → current cell is a border
• If an adjacent position has a different color → current cell is a border
• If an adjacent position has the same color and hasn't been visited → continue DFS to that cell

By using a vis (visited) array, we ensure we don't revisit cells and get stuck in cycles. The beauty of this approach is that we simultaneously:

1. Traverse the entire connected component
2. Identify which cells are borders
3. Color the borders in a single pass

The DFS naturally handles the recursive nature of exploring connected regions - each cell leads us to its same-colored neighbors, which lead to their neighbors, and so on, until we've mapped out the entire component and identified all its border cells.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation uses a DFS (Depth-First Search) approach with a visited tracking mechanism. Let's walk through the key components:

Data Structures:

• vis: A 2D boolean array of the same size as the grid to track visited cells, preventing infinite loops and redundant processing
• The original grid is modified in-place to store the result

Main Function Setup:

m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dfs(row, col, grid[row][col])

We initialize the visited array and start DFS from the given starting position, passing the original color of that cell.

DFS Function Logic: The recursive dfs(i, j, c) function takes the current position (i, j) and the original color c of the connected component.

1. Mark as visited: vis[i][j] = True ensures we don't process the same cell twice

2. Explore all 4 directions: Using pairwise((-1, 0, 1, 0, -1)) generates the four direction pairs: (-1, 0), (0, 1), (1, 0), (0, -1) representing up, right, down, and left movements

3. For each adjacent cell (x, y):

   • If within bounds (0 <= x < m and 0 <= y < n):
     • If not visited:
       • If it has the same color (grid[x][y] == c): Recursively explore it with dfs(x, y, c)
       • If it has a different color: Mark current cell as border by setting grid[i][j] = color
   • If out of bounds: The current cell is on the grid edge, so mark it as border with grid[i][j] = color

Key Implementation Details:

• The algorithm cleverly identifies border cells by checking their neighbors during traversal
• Border cells are colored immediately when identified
• Non-border cells (interior cells completely surrounded by same-colored cells) remain unchanged
• The pairwise function efficiently generates consecutive pairs from the direction array

Time Complexity: O(m × n) where each cell is visited at most once Space Complexity: O(m × n) for the visited array and O(min(m, n)) for the recursion stack in the worst case

The solution elegantly combines traversal and border detection in a single pass, modifying the grid in-place to achieve the desired result.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Initial Setup:

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

We want to find the connected component starting at grid[0][1] (value = 2) and color its border with color 4.

Step 1: Initialize

• Create visited array: vis = [[False, False, False], [False, False, False]]
• Start DFS at position (0, 1) with original color c = 2

Step 2: DFS at (0, 1)

• Mark visited: vis[0][1] = True
• Check all 4 neighbors:
  • Up (-1, 1): Out of bounds → Current cell is border! Set grid[0][1] = 4
  • Right (0, 2): In bounds, not visited, grid[0][2] = 2 (same color) → Continue DFS
  • Down (1, 1): In bounds, not visited, grid[1][1] = 3 (different color) → Current cell is border! (already set to 4)
  • Left (0, 0): In bounds, not visited, grid[0][0] = 1 (different color) → Current cell is border! (already set to 4)

Step 3: DFS at (0, 2)

• Mark visited: vis[0][2] = True
• Check all 4 neighbors:
  • Up (-1, 2): Out of bounds → Current cell is border! Set grid[0][2] = 4
  • Right (0, 3): Out of bounds → Current cell is border! (already set to 4)
  • Down (1, 2): In bounds, not visited, grid[1][2] = 2 (same color) → Continue DFS
  • Left (0, 1): In bounds, already visited → Skip

Step 4: DFS at (1, 2)

• Mark visited: vis[1][2] = True
• Check all 4 neighbors:
  • Up (0, 2): In bounds, already visited → Skip
  • Right (1, 3): Out of bounds → Current cell is border! Set grid[1][2] = 4
  • Down (2, 2): Out of bounds → Current cell is border! (already set to 4)
  • Left (1, 1): In bounds, not visited, grid[1][1] = 3 (different color) → Current cell is border! (already set to 4)

Final Result:

grid = [[1, 4, 4],
        [2, 3, 4]]

The connected component of 2's starting at (0, 1) included cells (0, 1), (0, 2), and (1, 2). All three cells were on the border because:

• (0, 1): Touches the top edge and cells with different colors
• (0, 2): Touches the top and right edges
• (1, 2): Touches the bottom and right edges, plus a cell with different color

Notice how the algorithm identifies border cells during traversal by checking each neighbor - if any neighbor is out of bounds or has a different color, the current cell gets colored immediately.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

The algorithm uses depth-first search (DFS) to traverse the connected component starting from (row, col). Each cell in the grid is visited at most once due to the vis array tracking visited cells. For each visited cell, we check at most 4 adjacent cells (up, down, left, right), which is a constant operation. Therefore, the total time complexity is O(m * n).

Space Complexity: O(m * n)

The space complexity consists of:

• The vis array which stores boolean values for all cells: O(m * n)
• The recursive call stack for DFS in the worst case (when all cells form a single connected component): O(m * n)

The dominant factor is O(m * n) for both the visited array and potentially the recursion stack depth, resulting in an overall space complexity of O(m * n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Premature Border Coloring Affecting Subsequent Checks

The Problem: The current implementation colors border cells immediately when detected. This can cause issues when the new color is the same as an adjacent component's color. Consider this scenario:

• Original grid has a component with color 1 next to a component with color 2
• We want to color the border of the color 1 component with color 2
• After coloring some border cells to 2, subsequent DFS calls might incorrectly identify interior cells as borders because they now appear adjacent to cells with color 2

Example:

Initial:     After some coloring:    Incorrect result:
1 1 2        2 1 2                   2 2 2
1 1 2   ->   2 1 2              ->   2 2 2
1 1 2        2 1 2                   2 2 2

Solution: Store border cells separately and color them after the entire DFS completes:

def colorBorder(self, grid, row, col, color):
    def dfs(curr_row, curr_col, original_color):
        visited[curr_row][curr_col] = True
        is_border = False
      
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for dx, dy in directions:
            next_row = curr_row + dx
            next_col = curr_col + dy
          
            if 0 <= next_row < rows and 0 <= next_col < cols:
                if not visited[next_row][next_col]:
                    if grid[next_row][next_col] == original_color:
                        dfs(next_row, next_col, original_color)
                    else:
                        is_border = True
                elif grid[next_row][next_col] != original_color:
                    # Check against original grid, not visited cells
                    is_border = True
            else:
                is_border = True
      
        if is_border:
            border_cells.add((curr_row, curr_col))
  
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    border_cells = set()
    original_color = grid[row][col]
  
    dfs(row, col, original_color)
  
    # Color all border cells after DFS completes
    for r, c in border_cells:
        grid[r][c] = color
  
    return grid

Pitfall 2: Not Handling Single-Cell Components

The Problem: A connected component might consist of just one cell. If this cell is surrounded by different colors or is on the grid edge, it should be colored. The current implementation handles this correctly, but it's easy to overlook when optimizing.

Example:

Grid:        Expected:
2 2 2        2 2 2
2 1 2   ->   2 3 2  (coloring with 3)
2 2 2        2 2 2

Pitfall 3: Incorrect Border Detection for Already-Visited Cells

The Problem: When checking adjacent cells, we need to distinguish between:

1. Cells that are part of our component (same original color)
2. Cells that are not part of our component (different color)

The current code only checks unvisited cells for different colors, potentially missing border detection when an already-visited cell of the same component is adjacent to a cell with a different color.

Solution: The improved solution above handles this by checking grid[next_row][next_col] != original_color even for visited cells, ensuring proper border detection throughout the component.