Last Updated: 31 Jul, 2020
Replace ‘O’ With ‘X’
Moderate
Asked in companies
Given a 2D array grid G of 'O's and 'X's. The task is to replace all 'O' with 'X' contained in each island. Where, an island is a set of 'O's connected horizontally or vertically and surrounded by 'X' from all of it's boundaries. (Boundary means top, bottom, left and right)
Example:
{{X, X, O, X, X, X},
{X, X, O, X, O, X},
{X, X, X, O, O, X},
{X, O, X, X, X, X},
{O, X, O, O, X, X},
{X, X, X, X, O, X}}
In the above example, there are 3 islands. Considering Zero based indexing of rows and columns, in the following islands described here, (x,y) represents the element in xth row and yth column.
Island 1: Formed by three elements at (1, 4), (2, 3), (2, 4) positions.
Island 2: Formed by a single element at (3, 1) position.
Island 3: Formed by two elements at (4, 2), (4, 3) positions.
Note:
In the above example, elements at positions (0, 2) and (1,2) do not form an island as there is no 'X' surronding it from the top.
Input Format:
The first line contains two integers 'N', 'M' representing the total number of rows and columns respectively.
Each of the next 'N' lines contains 'M' space-separated characters describing rows of the grid 'G' (each element of G is either 'O' or 'X').
Output Format:
Print 'N' lines each contain 'M' space-separated characters describing the rows of replaced grid 'G'.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'N', 'M' <= 1000
Time Limit: 1 sec
Approaches
- First, make a new 2D array of the same size as the input array. Let it be called arr. The input array will be called the matrix.
- Then, we'll iterate through ‘matrix’ and check the value of the current element.
- If it's equal to X, we'll assign arr as X at the same index.
- Otherwise, we'll check whether there exists a path from the current element to any edge element (edge elements are the ones that are present in either the first row/column or the last row/column) such that all elements in the path are equal to O.
- If such a path exists, we'll assign arr as O at the same index, otherwise, we'll assign arr as X
- Finally, copy all elements of arr to the matrix.
This problem is similar to the Flood fill Algorithm,
- First, we will be traversing the given matrix and replacing all O with R or any symbol other than O and X.
- For each edge in the given matrix, (Note: A matrix has four edges, the first row, the last row, the first column, and the last column)
- For every R in the current edge,
- Visit all adjacent cells/entries(left, right, top, down) recursively if there is R and replace them with O.
- For every R in the current edge,
- Traverse the modified matrix and replace all R with X.