MS paint code asked in an interview

Tag: algorithm Author: w2152405 Date: 2012-02-14

I had an interview today and was asked this question!

code the MS Paint program. N*N pixels area. given pixel and color, change color in pixel to desired color and if adjacent pixels are of same color change them too.

i approached it by saying i ll take a n* n array and would check for the pixel given and move to the the adjacent. for example the pixel given is x,y i would first check for the color in x,y in the array and next look for (x+1,y+1),(x+1,y),(x,y+1),(x-1,y),(x-1,y-1)....

but the interviewer was not happy can someone suggest me another way with a better algorithm.. which has better space and time complexity!

Best Answer

The interviewer was probably asking for flood-fill, which cannot be done with so simple an approach.

If this is flood-fill, diagonal doesn't count as adjacent.

The simplest flood-fill is a recursive call on each adjacent pixel on the array. Using the simple way on a large grid is very likely to run out of stack.

The right way is to enqueue the starting location, then dequeue, check if pixel color is still source color, and scan left and right filling as you go, and enqueue all pixels above and below. Continue until queue is drained.

Other Answer1

The algorithm you're talking about is called flood fill. Well-known approaches are discussed at Wikipedia.

Other Answer2

You can use DFS algorithm to solve this problem. Given a pixel (xi, yi), You can always construct the graph such that pixel node (xi-1, yi-1), (xi-1, yi), (xi, yi+1), (xi+1, yi), (xi+1, yi-1), (xi+1, yi+1), (xi-1, yi+1) and (xi, yi-1) as adjacent pixel nodes to (xi, yi). Execute the DFS starting from node (xi, yi) colouring each node in path and backtrack once you hit different colour node. DFS has a good time complexity of O(V+E).