D
DevExCode

LeetCode 1034: Coloring A Border Solution

Master LeetCode problem 1034 (Coloring A Border), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the connected component containing the cell at position (row, col) in the grid. While traversing, we identify the border cells of the connected component and change their color to the specified color.

Here are the steps for the algorithm:

  1. Perform a DFS starting from the given cell (row, col) to identify the connected component.
  2. During the DFS traversal, mark the border cells by comparing each cell with its adjacent cells. If a cell has a different color from any of its adjacent cells or it's on the boundary of the grid, it is considered a border cell.
  3. Change the color of all identified border cells to the specified color.

The time complexity of this algorithm is O(m * n) where m and n are the dimensions of the grid. The space complexity is O(m * n) for the recursive stack space used in the DFS traversal.

:

Solution Code

class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int originalColor = grid[row][col];
        dfs(grid, row, col, originalColor);
        
        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 originalColor) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != originalColor) {
            return;
        }
        
        grid[i][j] = -originalColor; // mark visited
        
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : dirs) {
            int newRow = i + dir[0];
            int newCol = j + dir[1];
            if (newRow < 0 || newCol < 0 || newRow >= grid.length || newCol >= grid[0].length || Math.abs(grid[newRow][newCol]) == originalColor) {
                continue;
            }
            dfs(grid, newRow, newCol, originalColor);
        }
        
        if (i > 0 && j > 0 && i < grid.length - 1 && j < grid[0].length - 1 &&
            Math.abs(grid[i-1][j]) == originalColor && Math.abs(grid[i+1][j]) == originalColor &&
            Math.abs(grid[i][j-1]) == originalColor && Math.abs(grid[i][j+1]) == originalColor) {
            grid[i][j] = originalColor;
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1034 (Coloring A Border)?

This page provides optimized solutions for LeetCode problem 1034 (Coloring A Border) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1034 (Coloring A Border)?

The time complexity for LeetCode 1034 (Coloring A Border) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1034 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1034 in Java, C++, or Python.

Back to LeetCode Solutions