Update appNew update is available. Click here to update.

Replace ‘O’ With ‘X’

Contributed by
Shivam Kumar Singh
Last Updated: 23 Feb, 2023
Medium
yellow-spark
0/80
Avg time to solve 35 mins
Success Rate 60 %
Share
16 upvotes

Problem Statement

Suggest Edit

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 )
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
Reset Code
Full screen
Auto
copy-code
Console