Coloring A Border

Medium

Booking.com

4 views

Topics:

ArraysGraphsRecursion

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.

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]]

Constraints:

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

Try coding it in LeetCode

Coloring A Border

Medium

Booking.com

4 views

Topics:

ArraysGraphsRecursion

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.

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]]

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what is the maximum possible value for grid[i][j]?
Is the given row and column (r0, c0) always a valid cell within the grid's boundaries?
What should the function return if the given cell (r0, c0) does not form part of a border (e.g., if the entire grid is just one cell)?
Is the new color 'color' guaranteed to be different from the original color of the connected component?
Are the grid dimensions guaranteed to be at least 1x1, or can they be empty?

Brute Force Solution

Approach

The brute force method for coloring a border involves checking every cell in a region to see if it's on the border. We will go through the entire grid and identify the cells that need to be recolored based on their location and neighbors.

Here's how the algorithm would work step-by-step:

Look at each square in the grid, one by one.
For each square, check if it's part of the main area that we're interested in coloring.
If the square is part of that area, check its neighbors (the squares directly above, below, left, and right of it).
If the square is on the edge of the grid, OR if any of its neighbors are NOT part of the main area, then this square is considered a border square.
Remember which squares are border squares.
After checking every square, change the color of all the border squares to the new color.

Code Implementation

def color_border_brute_force(grid, row, column, color):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    initial_color = grid[row][column]
    border_cells = []

    for current_row in range(number_of_rows):
        for current_column in range(number_of_columns):
            if grid[current_row][current_column] == initial_color:
                # Check neighbors to identify borders

                is_border = False

                if current_row == 0 or current_row == number_of_rows - 1 or \
                   current_column == 0 or current_column == number_of_columns - 1:
                    is_border = True
                else:
                    if grid[current_row - 1][current_column] != initial_color or \
                       grid[current_row + 1][current_column] != initial_color or \
                       grid[current_row][current_column - 1] != initial_color or \
                       grid[current_row][current_column + 1] != initial_color:
                        is_border = True

                if is_border:
                    border_cells.append((current_row, current_column))

    # Change the color of the border cells

    for border_row, border_column in border_cells:
        grid[border_row][border_column] = color

    return grid

Big(O) Analysis

Time Complexity

O(m*n) – Let m be the number of rows and n be the number of columns in the grid. The brute force approach iterates through each cell in the grid, resulting in m*n operations to visit every cell. For each cell, a constant number of neighbor checks (up to four) are performed to determine if the cell is a border cell. Since neighbor checking is a constant time operation, the overall time complexity is dominated by the initial grid traversal, which is proportional to the total number of cells in the grid. Thus, the time complexity approximates m*n operations and is O(m*n).

Space Complexity

O(N) – The brute force method, as described, identifies and remembers border squares before recoloring. This implies storing the coordinates (or references) of these border squares in an auxiliary data structure, such as a list or set. In the worst-case scenario, the entire grid might consist of border squares, leading to storage proportional to the total number of cells in the grid. Thus, we have an auxiliary array of size N, where N represents the total number of cells in the grid (rows * cols), to keep track of border cells, resulting in O(N) space complexity.

Optimal Solution

Approach

To efficiently color the border of a connected region in a grid, we first identify the connected region starting from a given cell. Then, we only color those cells that are on the border of this region.

Here's how the algorithm would work step-by-step:

Start at the given cell and find all connected cells that have the same color as the starting cell. This identifies the entire connected region.
For each cell in the connected region, check its neighbors (up, down, left, right).
If a cell is next to a cell with a different color, or if it is on the edge of the entire grid, then it's on the border.
Change the color of only the border cells to the new color.

Code Implementation

def color_border(grid, row, column, color):
    original_color = grid[row][column]
    visited = set()
    rows = len(grid)
    columns = len(grid[0])

    def depth_first_search(row_index, column_index):
        if not (0 <= row_index < rows and 0 <= column_index < columns and grid[row_index][column_index] == original_color and (row_index, column_index) not in visited):
            return

        visited.add((row_index, column_index))
        is_border = False

        # Check neighbors to determine if current cell is a border cell
        if row_index == 0 or row_index == rows - 1 or column_index == 0 or column_index == columns - 1:
            is_border = True
        else:
            if grid[row_index - 1][column_index] != original_color or \
               grid[row_index + 1][column_index] != original_color or \
               grid[row_index][column_index - 1] != original_color or \
               grid[row_index][column_index + 1] != original_color:
                is_border = True

        # Color the border cell after the entire region is explored
        depth_first_search(row_index + 1, column_index)
        depth_first_search(row_index - 1, column_index)
        depth_first_search(row_index, column_index + 1)
        depth_first_search(row_index, column_index - 1)

        if is_border:
            grid[row_index][column_index] = color

    # Initiate depth first search to traverse connected region
    depth_first_search(row, column)
    return grid

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm performs a Depth-First Search (DFS) or Breadth-First Search (BFS) to identify the connected region. In the worst case, the connected region spans the entire grid. The grid dimensions are 'm' rows and 'n' columns. Visiting each cell in the grid during the search takes O(m*n) time. After identifying the connected region, the algorithm iterates through each cell in the connected region (again, potentially all m*n cells) and checks its neighbors, taking constant time O(1) for each neighbor. Thus the total runtime is proportional to the number of cells in the grid, making the time complexity O(m*n).

Space Complexity

O(N) – The algorithm uses a recursive approach or a queue (implicitly suggested by 'find all connected cells') to perform a Breadth-First Search (BFS) or Depth-First Search (DFS) to identify the connected region. In the worst-case scenario, the entire grid might be a single connected region, requiring the algorithm to store all N cells of the grid in the recursion stack (for DFS) or in the queue (for BFS), where N is the total number of cells in the grid. Additionally, a set or a similar data structure might be implicitly used to keep track of visited cells, potentially storing up to N elements in the worst case. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty grid input	Return the input grid itself as there's nothing to process.
Grid with only one cell	Check if the single cell's value matches the target color and color it if it does; otherwise return the original grid.
All cells in the grid have the same color, different from the target color	No border exists, so return the original grid.
All cells in the grid have the same color, equal to the target color	Color all cells in the grid to the new color because the entire grid is the border.
The given row and column are out of bounds	The start point is invalid, so return the original grid without modification.
Grid with very large dimensions exceeding memory constraints	The algorithm should avoid excessive memory allocation and utilize in-place modifications if possible to optimize memory usage.
Integer overflow when calculating indices or sizes	Ensure all index calculations are done using appropriate data types to prevent integer overflow and potentially wrap around to negative values.
Stack overflow due to deep recursion (DFS) on large grids	Convert recursive DFS to iterative DFS with an explicit stack to avoid stack overflow errors.