Replace ‘O’ With ‘X’

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
48 upvotes
Asked in companies
RazorpayIntuitDTCC

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
5 4
X X O O
X O X X
X O O X
X O X X
X X X X
Sample Output 1:
X X O O
X X X X
X X X X
X X X X
X X X X
Explanation of Sample Output 1:
There is only one island in the above input. Considering zero based indexing, The co-ordinates of the island are (1, 1), (2, 1), (2, 2) and (3, 1). We just need to replace the O's at this co-ordinates with X's. Hence the output.
Sample Input 2:
3 4
X X O X
X O X X
X X O O
Sample Output 2:
X X O X
X X X X
X X O O
Hint

Visit all ‘O’ entries in the matrix and check recursively whether to replace or not.

Approaches (2)
Recursive Approach
  1. 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.
  2. Then, we'll iterate through ‘matrix’ and check the value of the current element.
    1. If it's equal to X, we'll assign arr as X at the same index.
    2. 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.
      1. If such a path exists, we'll assign arr as O at the same index, otherwise, we'll assign arr as X
  3. Finally, copy all elements of arr to the matrix.
Time Complexity

O(N^2*M^2), where N, M is the number of rows and columns respectively.

 

In the worst case, for each entry in the matrix, we will be visiting all paths from that cell to an edge cell. (In all paths it can only include at most N * M cells. O((N * M)* ((N * M) )).

Space Complexity

O(N * M), where N, M is the number of rows and columns respectively.

 

All changes are done in the new matrix of N rows and M columns. Also, the Recursive calls can go to a maximum depth of N*M(call all cells), thus requiring a space of Recursive N*M for the stack.

Code Solution
(100% EXP penalty)
Replace ‘O’ With ‘X’
Full screen
Console