Border Color

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in company
Facebook

Problem statement

You are given an N*M matrix where the cell (i,j) is colored by MATRIX[i][j]. You have to color the border of the connected component which contains the cell (ROW, COL) with the color NEW_COLOR. Two squares belong to the same connected component if they have the same color and are next to each other in any of the 4 directions (top, down, left, right).

Example:- 
N = 2, M = 2, NEW_COLOR = 3, ROW = 0, COL = 0 
MATRIX = [[1,1],[1,2]]
ANSWER:- The answer should be [[3,3],[3,2]] because the connected component is the cells with indices (0,0),(0,1) and (1,0).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains five integers ‘N’, ‘M’, ‘NEW_COLOR’, ‘ROW’, ‘COL’ denoting the number of rows and columns in the matrix, the new color that will be applied to the borders of the connected component, and the coordinates of the cell which the connected component contains respectively.

The next ‘N’ lines of every test case contain ‘M’ integers which denote MATRIX[i][j], the color cell (i,j) is currently colored.
Output Format : 
For each test case, return a matrix of N*M with the colors of the cells updated..

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 500
1 <= M <= 500
1 <= MATRIX[i][j] <= 10^9
1 <= NEW_COLOR <= 10^9
1 <= ROW <= N
1 <= COL <= M

Time Limit =  1sec
Sample Input 1 :
2
2 3 3 0 1
1 2 2
2 3 2
3 3 2 1 1
1 1 1
1 1 1
1 1 1
Sample Output 1 :
1 3 3
2 3 3
2 2 2
2 1 2
2 2 2
Explanation for Sample Output 1 :
In the first test case, the connected components are the cells (0,1),(0,2), and (1,2), so its borders are colored.
In the second test case, the whole matrix is connected, so its borders are colored.
Sample Input 2 :
1
1 3 3 0 1
1 2 3
Sample Output 2 :
1 3 3
Hint

Check which cells are connected with the cell (row, col).

Approaches (1)
Breadth-first Search

Use breadth-first search to find which cells are connected with (row, col). Then check whether those cells lie on the border of the connected component or not. If yes, change their colors.

 

Algorithm:-

 

  1. Initialize an empty QUEUE. Insert (row, col) in the queue.
  2. Initialize a 2D array named ANS with N*M dimensions.
  3. Start a while loop while the QUEUE is not empty.
    1. Pop-out the first element in the QUEUE.
    2. If the neighbor of the currently popped cell is of the same color, mark it as connected and add it to the QUEUE.
  4. Iterate from 0 to N(Let’s say the iterator is i).
    1. Iterate from 0 to M.(Let’s say the iterator is j).
      1. Count the number of neighboring cells with the same color.
      2. If the count of such cells is less than 4 and the cell is connected, set ANS[i][j] as NEW_COLOR.
      3. Otherwise, update ANS[i][j] as MATRIX[i][j].
  5. Return the ANS.
Time Complexity

O(N*M), where N and M are the dimensions of the matrix.

We are through every cell of the matrix, so the time complexity is O(N*M).

Space Complexity

O(N*M), where N and M are the dimensions of the matrix.

We are using a deque for breadth-first search which can grow up to a size of N*M, so the space complexity is O(N*M).

Code Solution
(100% EXP penalty)
Border Color
Full screen
Console