MS paint code asked in an interview

Question

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!

Answer 1

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.