By: Saurav

2018-03-20 04:47:00 UTC

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].


This problem is among those which are verbose but actually are very simple and direct implementation of an algorithm.
The algo used here is DFS.

The only caveat is that if the image has 1 and 0 and the new color is among those two, depending upon the location of start, the recursion may become infinite.

To tackle the problem, it's better to use a buffer color value like -11, which I used and then replace that color value with the new value after all recursion is done.

Let's see it in action:

def flood_fill(image, sr, sc, new_color)
    return image if image.length < 1 or image[0].length < 1
    color = image[sr][sc]
    arr = dfs(image, sr,sc,color, -11)
    arr =  arr.map{|i| i.map{|j| j == -11 ? new_color : j}}
    return arr

def dfs(image, sr,sc,color, new_color)
  x = [1,-1,0,0]
  y = [0,0,1,-1]
  image[sr][sc]  = new_color
  (0..x.length-1).each do |index|
    if sr+x[index] >= 0 and sr+x[index] < image.length and sc+y[index] >= 0 and sc+y[index] < image[0].length and (image[sr+x[index]][sc+y[index]] == color)
      #p "dfs(#{image}, #{sr},#{sc},#{color}, #{new_color})"
      dfs(image, sr+x[index],sc+y[index],color, new_color)
  return image

To see the stack state during each recursion or to see how DFS works, uncomment the line p "dfs(#{image}, #{sr},#{sc},#{color}, #{new_color})".

We can take out the array initialization as a constant for refactoring rather than initializing it each time in DFS but it works fine.

For fun, uncomment the line in the code and then run it with the test cases below:


Let me know what you think!
twitter: sprakash24oct

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)