DEV Community

loading...

6-10PM challenge problem #003

akbhairwal profile image akbhairwal Updated on ・1 min read

Taking the difficulty level little higher. Today I am sharing a graph problem.

Island Count

A binaryMatrix which is 2D array of 0s and 1s. You need to find the number of island of 1s in this matrix.
Example input:

binaryMatrix =     [ [0,    1,    0,    1,    0],
                     [0,    0,    1,    1,    1],
                     [1,    0,    0,    1,    0],
                     [0,    1,    1,    0,    0],
                     [1,    0,    1,    0,    1] ]

An island can be defined as a group of adjacent values of all 1s.

Two cells, which have same value and next to each other in a single row or column are adjacent. (Diagonal two cells which have same value can't be considered as adjacent cells)

Explain and code the most efficient solution possible and analyze its time and space complexities.

[time limit] 5000ms

[input] array.integer arr

0 ≤ arr.length ≤ 20
[output] array.integer

Input : Above matrix

output 6 # since this is the number of islands in binaryMatrix.

Solution

Discussion (0)

pic
Editor guide