Good evening! Here's our prompt for today.

Challenge: Finding the Largest Island of Connected Ones in a Matrix

Introduction

Imagine you're an explorer on a digital ocean filled with islands made up of ones (1s) and water represented by zeroes (0s). Your task is to find the largest island composed of connected 1s in a given 2D grid (or matrix).

Here's a sample grid:

1const matrix = [
2  [1, 1, 0, 0, 0],
3  [0, 1, 1, 0, 0],
4  [0, 1, 0, 1, 0],
5  [1, 0, 0, 0, 0]
6];

Your Task

Write a class or method called MostConnectedOnes(matrix: array[]) that identifies the largest island of connected 1s in this digital ocean.

Defining "Connected"

Two 1s are considered connected if one is positioned:

1. Above the other
2. Below the other
3. To the left of the other
4. To the right of the other

Note: Diagonal connections do not count!

Examples

In the very first sample grid, the largest island has a size of 5. The connected 1s can be found starting at [0][0], moving right to [0][1], down to [1][1], right to [1][2], and finally down again to [2][1].

1const matrix = [
2  [1, 1, 0, 0, 0],
3  [0, 1, 1, 0, 0],
4  [0, 1, 0, 1, 0],
5  [1, 0, 0, 0, 0]
6];

Here's another example:

1const matrix = [
2  [1, 1, 0, 0],
3  [0, 0, 1, 0],
4  [0, 1, 1, 0],
5  [1, 0, 0, 0]
6];
7
8const mco = new MostConnectedOnes(matrix);
9mco.max();
10// Output: 3

Constraints

• The total number of elements in the matrix will be <= 100000
• The value of each element inside the matrix will either be 0 or 1
• If n is the number of rows and m is the number of columns, the expected time and space complexity should be O(n * m)

Your task is to find the "area" or the size of the largest island of connected 1s in the given matrix.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

class MostConnectedOnes:

    def __init__(self, matrix):

        self.matrix = matrix

        self.processed = []

​

    def max_ones(self):

        # fill in

        return

​

​

import unittest

​

​

class Test(unittest.TestCase):

    def test_1(self):

        assert (

            MostConnectedOnes(

                [[1, 1, 0, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 0]]

            )

            == 5

        )

        print(

            "PASSED: `MostConnectedOnes([[1,1,0,0,0], [0,1,1,0,0], [0,1,0,1,0], [1,0,0,0,0]])` should return `5`"

        )

​

    def test_2(self):

        assert (

            MostConnectedOnes([[1, 1, 0, 0], [0, 0, 1, 0], [0, 1, 1, 0], [1, 0, 0, 0]])

            == 3

We'll now take you through what you need to know.

How do I use this guide?