Grokking Graph Algorithms for Coding Interviews

0% completed

​

Biggest Island (easy)

Problem Statement

Given a 2D array (i.e., a matrix) containing only 1s (land) and 0s (water), find the biggest island in it. Write a function to return the area of the biggest island. 

An island is a connected set of 1s (land) and is surrounded by either an edge or 0s (water). Each cell is considered connected to other cells horizontally or vertically (not diagonally).

Example 1

Input: matrix =

Output: 5
Explanation: The matrix has three islands. The biggest island has 5 cells .

Constraints:

  • m == matrix.length
  • n == matrix[i].length

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Alan Ross

· 4 years ago

BFS examples seem to be missing on this problem, any plans to add them in as it is mentioned?

Show 2 replies
T

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def maxAreaOfIsland(self, matrix):
    biggestIslandArea = 0
    # TODO: Write your code here
    # loop through matrix to see if we can find an island
    # call visitNeighborIsland to calculate the size of island
    for row in range(len(matrix)):
      for col in range(len(matrix[0])):
        if matrix[row][col] == 1:
          currSizeIsland = self.visitNeighborIslandBFS(row, col, matrix)
          biggestIslandArea = max(biggestIslandArea, currSizeIsland)
    return biggestIslandArea
  
  def visitNeighborIslandDFS(self, row, col, matrix, currSize):
    if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
      return 0
    if matrix[row][col] == 0:
      return 0
    currSize = 1
    matrix[row][col] = 0
Tobby Lie

Tobby Lie

· 2 years ago

The BFS solution provided seems unnecessarily complicated, this is what I have in Python that has a space complexity of O(min(m, n)) rather than the O(m * n) described in the solution...

from collections import deque

class Solution:
  def maxAreaOfIsland(self, matrix):
    biggestIslandArea = 0
    rows = len(matrix)
    cols = len(matrix[0])
    for i in range(rows):
      for j in range(cols):
        if matrix[i][j] == 1:
          biggestIslandArea = max(biggestIslandArea, self.visit_land_bfs(matrix, i, j))
    return biggestIslandArea

  def visit_land_bfs(self, matrix, x, y):
    neighbors = deque([(x, y)])
    area = 0

    while neighbors:
      x, y = neighbors.popleft()

      if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]):
        continue
      if mat
K

krishnakeshav.pes

· 3 years ago

complexity to traverse matrix in O(mxn) and then bfs/dfs is performed on each cell. But we only visit each cell once so, let's say average length is x and no. of islands is y. So, the complexity will be O(x * y) for bfs/dfs. Thus, overall complexity will be O(mnxy).

Can you please help me understand how complexity is being calculated here ?

Show 1 reply
V

venkat narsim

· 3 years ago

class Solution {
  maxAreaOfIsland(matrix) {
    let biggestIslandArea = 0;
    let islandCounter = [];
    let row = matrix.length;
    let col = matrix[0].length;
    let visitedMatrix = Array(row).fill(false).map(() => Array(col).fill(false));
    for(let i=0; i<row; i++) {
        for(let j=0; j<col; j++) {
            if(matrix[i][j] === 1 && visitedMatrix[i][j] === false) {
                biggestIslandArea = visitedMatrixFiller(matrix, visitedMatrix, biggestIslandArea, i,j);
                islandCounter.push(biggestIslandArea);
                biggestIslandArea = 0;
            }
        }
    }
    console.log(islandCounter); --> This produces [4,1,5]
    return Math.max(islandCounter); --> This produces null
  }
}

function visitedMatrixFiller(matrix, visitedMatrix,