Islands in a Graph

[ramitsawhney27]

Given:
A grid of size n x m. Each cell is either Red or Blue. Red is denoted as * and . as Blue.
The entire grid is surrounded in blue.
A collection of blue cells surrounded by red on all sides is considered a pool.

Tasks:

1. Count the total number of pools in the grid.
2. Return the size of each of the pools in the grid.
3. Time and Space complexities for each of these operations.

Sample:
5 4

****
*..*
****
*.**
..**

Number of pools: 1; size = 2

[aggmoulik]

I think 4th row is incomplete

[h-sinha]

@ramitsawhney27 it would be really helpful if you update the fourth line of the test case

[ramitsawhney27]

@h-sinha @moulikcipherX fixed.

[h-sinha]

Shouldn't the number of pools be 1 in this case? As the '.' in 4th row has a '.' on one side.

[ramitsawhney27]

The two pools are in row 2 and row 4 of size 2 and 1 respectively. The one in the 5th row is not counted.

[lavishsaluja]

@ramitsawhney27 Will like to work on this!

[ghost]

This is still open, right?

[sahilbansal17]

Challenge problems are open for anyone. Whosoever solves and sends the PR earliest, will get the points.

[ghost]

Yeah I meant to ask whether it has been solved already or not

[ramitsawhney27]

Not yet

[ghost]

How is the one in the 4th row even a pool? It's not surrounded by red on all sides..

[ramitsawhney27]

I just realized, markdown messes up how it's being shown. Something to do with the \ and *. I've edited it. Ideally, the . should be on the 3rd column in the 4th row. Then the solution is correct for what was given previously.

[ghost]

Okay, and diagonally blue is okay for a pool?

[ramitsawhney27]

Just keep it as up down left right (4-connectivity) for simplicity.

[ramitsawhney27]

This is solved, closing it.