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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Coloring A Border

Number: 1104

Difficulty: Medium

Paid? No

Companies: Booking.com

Problem Description

Given an m x n grid where each cell has a color value, the goal is to change the color of the border of the connected component that includes the cell grid[row][col]. A connected component consists of cells with the same color that are adjacent (up, down, left, right). A cell is considered a border if it is either adjacent to a cell of a different color or lies on the boundary of the grid.

Key Insights

  • Identify the connected component starting from grid[row][col] using DFS or BFS.
  • A cell is on the border if any of its 4 adjacent cells is either out-of-bounds or has a different color.
  • After determining all border cells, update their color while keeping the internal area unchanged.
  • Tracking visited cells prevents unnecessary reprocessing and infinite loops.

Space and Time Complexity

Time Complexity: O(mn) in the worst case, where m and n are the number of rows and columns. Space Complexity: O(mn) due to the recursion stack (in DFS) or queue (in BFS) and the visited structure.

Solution

We solve the problem by first performing a DFS (or BFS) starting at the given cell (row, col) to traverse its connected component. During the traversal, we check for each cell whether it qualifies as a border cell. A cell is a border cell if:

  • It is on the boundary of the grid.
  • At least one of its 4 neighbors is not of the same original color. After collecting all the border cells, their color is updated to the given new color. The use of DFS (or BFS) ensures that every cell in the connected component is visited exactly once, resulting in an efficient solution.

Code Solutions

def colorBorder(grid, row, col, color):
    # Get grid dimensions.
    m, n = len(grid), len(grid[0])
    # Record the original color of the starting cell.
    orig = grid[row][col]
    # List to store all border cells.
    borders = []
    # 2D visited matrix to avoid processing a cell more than once.
    visited = [[False] * n for _ in range(m)]
    
    # Helper function for DFS traversal.
    def dfs(r, c):
        visited[r][c] = True
        isBorder = False
        # Define directions: up, down, left, right.
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check if neighbor is out-of-bound.
            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                isBorder = True
            # Check if neighbor color is different.
            elif grid[nr][nc] != orig:
                isBorder = True
            # Proceed with DFS if neighbor is unvisited.
            elif not visited[nr][nc]:
                dfs(nr, nc)
        # If the cell is a border, add it to the borders list.
        if isBorder:
            borders.append((r, c))
    
    # Start DFS from the given starting cell.
    dfs(row, col)
    
    # Update the color of all border cells.
    for r, c in borders:
        grid[r][c] = color
        
    return grid

# Example usage:
# grid = [[1,1],[1,2]]
# print(colorBorder(grid, 0, 0, 3))
← Back to All Questions