Back to course sections
    Mark As Completed Discussion

    Good morning! 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:

    JAVASCRIPT
    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.

    Description

    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!

    Description

    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].

    JAVASCRIPT
    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:

    JAVASCRIPT
    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?

    JAVASCRIPT
    OUTPUT
    :001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

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

    How do I use this guide?

    Access all course materials today

    The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

    Returning members can login to stop seeing this.