Medium · Grid DFS
Understand → Visualise → Practice.
Recolour the orthogonally connected component containing the starting cell.
Starting from the given cell, visit every orthogonal neighbour that has the original colour and recolour it, using a stack or recursion.
If it already equals the new colour, return the image unchanged (this also avoids an endless loop).
Colour the start cell and push it on a stack.
Pop a cell; recolour and push each in-bounds neighbour still holding the old colour.
O(rows × cols) time and O(rows × cols) space.
Not handling 'new colour == old colour' revisits cells forever.
Read the full guide first: Matrices and 2-D Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.