We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Coloring A Border

Difficulty: Medium

Problem Description

You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location. Two squares are called adjacent if they are next to each other in any of the 4 directions. Two squares belong to the same connected component if they have the same color and they are adjacent. The border of a connected component is all the squares in the connected component that are either adjacent to (at least) a square not in the component, or on the boundary of the grid (the first or last row or column). You should color the border of the connected component that contains the square grid[row][col] with color. Return the final grid.

Key Insights

  • A connected component is defined by adjacent squares of the same color.
  • The border consists of squares in the connected component that are adjacent to a different color or are on the edge of the grid.
  • Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to explore and mark the connected component.
  • Special care must be taken to identify border squares while traversing the component.

Space and Time Complexity

Time Complexity: O(m * n) - We may need to traverse the entire grid in the worst case. Space Complexity: O(m * n) - The recursive stack or queue may use space proportional to the size of the grid.

Solution

To solve the problem, we need to use a graph traversal technique such as Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the connected component starting from the given cell (row, col). During the traversal, we keep track of border squares by checking if any adjacent cell is either out of bounds, has a different color, or is on the grid boundary. After identifying all border squares, we will change their colors to the specified color.

Code Solutions

def colorBorder(grid, row, col, color):
    m, n = len(grid), len(grid[0])
    original_color = grid[row][col]
    visited = set()
    borders = set()
    
    def dfs(r, c):
        if (r, c) in visited:
            return
        visited.add((r, c))
        is_border = False
        
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            
            if nr < 0 or nr >= m or nc < 0 or nc >= n or grid[nr][nc] != original_color:
                is_border = True
            elif (nr, nc) not in visited:
                dfs(nr, nc)
        
        if is_border:
            borders.add((r, c))

    dfs(row, col)
    
    for r, c in borders:
        grid[r][c] = color
    
    return grid
← Back to All Questions