Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Coloring A Border

Posted on August 5, 2019July 26, 2020 by braindenny

Coloring A Border



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #graph, #dfs, #colorgraph

Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.

Example 1:

Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
Output: [[3, 3], [3, 2]]

Example 2:

Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
Output: [[1, 3, 3], [2, 3, 3]]

Example 3:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]

Note:

1 1 <= grid.length <= 50

  • 1 <= grid[0].length <= 50
  • 1 <= grid[i][j] <= 1000
  • 0 <= r0 < grid.length
  • 0 <= c0 < grid[0].length
  • 1 <= color <= 1000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// https://code.dennyzhang.com/coloring-a-border
// Basic Ideas: dfs
//
// Coloring an island. Instead of all region, but only the boarders
// Notice: not typical boarders. The cell need to be fully connected
// Notice: the color would exist in other islands of this same graph
//
// Complexity: Time O(n), Space O(n)
func abs(x int) int {
    if x<0 {
        return -x
    } else {
        return x
    }
}
func dfs(grid [][]int, r int, c int, color int) {
    // move out of boundry
    if r<0 || r>=len(grid) || c<0 || c>=len(grid[0]) {
        return
    }
    if grid[r][c] != color {
        return
    }
    grid[r][c] = -color // visiting
    dfs(grid, r+1, c, color)
    dfs(grid, r-1, c, color)
    dfs(grid, r, c+1, color)
    dfs(grid, r, c-1, color)
    // change back, for non-boarder nodes
    if r>0 && r<len(grid)-1 && c>0 && c<len(grid[0])-1 && 
        abs(grid[r+1][c]) == color && abs(grid[r-1][c]) == color &&
        abs(grid[r][c+1]) == color && abs(grid[r][c-1]) == color {
        grid[r][c] = color
    }
}

func colorBorder(grid [][]int, r0 int, c0 int, color int) [][]int {
    // grid won't be empty, empty lines, empty roles.
    // (r0, c0) is a valid position
    dfs(grid, r0, c0, grid[r0][c0])
    for i, row := range grid {
        for j, v := range row {
            if v<0 {
                grid[i][j] = color
            }
        }
    }
    return grid
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #dfs, #graph, colorgraph

Post navigation

LeetCode: Queens That Can Attack the King
LeetCode: Critical Connections in a Network

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.