Mark As Completed Discussion

Good afternoon! 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.