1034. Coloring A Border LeetCode Solution

In this guide, you will get 1034. Coloring A Border LeetCode Solution with the best time and space complexity. The solution to Coloring A Border problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Coloring A Border solution in C++
Coloring A Border solution in Java
Coloring A Border solution in Python
Additional Resources

1034. Coloring A Border LeetCode Solution image

Problem Statement of Coloring A Border

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1034. Coloring A Border LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0,
                                  int color) {
    dfs(grid, r0, c0, grid[r0][c0]);

    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j)
        if (grid[i][j] < 0)
          grid[i][j] = color;

    return grid;
  }

 private:
  void dfs(vector<vector<int>>& grid, int i, int j, int startColor) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return;
    if (grid[i][j] != startColor)
      return;

    grid[i][j] = -startColor;
    dfs(grid, i + 1, j, startColor);
    dfs(grid, i - 1, j, startColor);
    dfs(grid, i, j + 1, startColor);
    dfs(grid, i, j - 1, startColor);

    // If this cell is already on the boarder, it must be painted later.
    if (i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1)
      return;

    if (abs(grid[i + 1][j]) == startColor &&  //
        abs(grid[i - 1][j]) == startColor &&  //
        abs(grid[i][j + 1]) == startColor &&  //
        abs(grid[i][j - 1]) == startColor)
      grid[i][j] = startColor;
  }
};
/* code provided by PROGIEZ */

1034. Coloring A Border LeetCode Solution in Java

class Solution {
  public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
    dfs(grid, r0, c0, grid[r0][c0]);

    for (int i = 0; i < grid.length; ++i)
      for (int j = 0; j < grid[0].length; ++j)
        if (grid[i][j] < 0)
          grid[i][j] = color;

    return grid;
  }

  private void dfs(int[][] grid, int i, int j, int startColor) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return;
    if (grid[i][j] != startColor)
      return;

    grid[i][j] = -startColor;
    dfs(grid, i + 1, j, startColor);
    dfs(grid, i - 1, j, startColor);
    dfs(grid, i, j + 1, startColor);
    dfs(grid, i, j - 1, startColor);

    // If this cell is already on the boarder, it must be painted later.
    if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1)
      return;

    if (Math.abs(grid[i + 1][j]) == startColor && //
        Math.abs(grid[i - 1][j]) == startColor && //
        Math.abs(grid[i][j + 1]) == startColor && //
        Math.abs(grid[i][j - 1]) == startColor)
      grid[i][j] = startColor;
  }
}
// code provided by PROGIEZ

1034. Coloring A Border LeetCode Solution in Python

class Solution:
  def colorBorder(
      self,
      grid: list[list[int]],
      r0: int,
      c0: int,
      color: int
  ) -> list[list[int]]:
    def dfs(i: int, j: int, startColor: int) -> None:
      if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
        return
      if grid[i][j] != startColor:
        return

      grid[i][j] = -startColor
      dfs(i + 1, j, startColor)
      dfs(i - 1, j, startColor)
      dfs(i, j + 1, startColor)
      dfs(i, j - 1, startColor)

      # If this cell is already on the boarder, it must be painted later.
      if i == 0 or i == len(grid) - 1 or j == 0 or j == len(grid[0]) - 1:
        return

      if (abs(grid[i + 1][j]) == startColor and
          abs(grid[i - 1][j]) == startColor and
          abs(grid[i][j + 1]) == startColor and
              abs(grid[i][j - 1]) == startColor):
        grid[i][j] = startColor

    dfs(r0, c0, grid[r0][c0])

    for i, row in enumerate(grid):
      for j, num in enumerate(row):
        if num < 0:
          grid[i][j] = color

    return grid
 # code by PROGIEZ