Grokking Graph Algorithms for Coding Interviews

0% completed

​

Solution: Number of Closed Islands

Problem Statement

You are given a 2D matrix containing only 1s (land) and 0s (water).

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

A closed island is an island that is totally surrounded by 0s (i.e., water). This means all horizontally and vertically connected cells of a closed island are water. This also means that, by definition, a closed island can't touch an edge (as then the edge cells are not connected to any water cell).

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Sri Harsha Bandarupalli

· 4 years ago

Could someone please explain why did they use "&" and why not "and"?

I tried using "and" i had got a different answer, instead of 1 and 2 i got 2 and 2.

Can someone please explain this?

Show 1 reply
A

arya.javadi80

· 3 years ago

Can you do this without visited and bitwise? I tried with marking the cells and returning True if all the DFS calls go through but I got 2,2 for tests??

Show 1 reply
Ivan Mariić

Ivan Mariić

· 3 years ago

This solution is not working when I copy and paste it to Leetcode

Show 1 reply
S

Sana Madhavan

· 4 years ago

Why do you have to use a visited boolean array in this case instead of setting the visited notes to zero?

Show 3 replies
D

Deko

· 4 years ago

It'd be nice to have some explanations about the part with the bitwise AND. Only the conditions for the recursion are explained. As far as I understood, if any of the four recursive calls returns false, it means that cell is not part of a closed island. Is this assumption correct?

Show 1 reply
Cristian Rodriguez

Cristian Rodriguez

· 3 years ago

What if we do not have a square matrix, example a 4 x 6 matrix?

Show 1 reply
T

Thai Minh

· 3 years ago

from collections import deque

class Solution:
  def countClosedIslands(self, matrix):
    countClosedIslands = 0
    # TODO: Write your code here
    # during the visit, we want to check if any node of island reside on the edge, then force return 0 if it is
    # Time complexity: O(row * col)
    # Space complexity: O(row * col) 
    for row in range(len(matrix)):
      for col in range(len(matrix[0])):
        if matrix[row][col] == 1:
          countClosedIslands += self.visitIsland(row, col, matrix)
    return countClosedIslands
  def visitIsland(self, row, col, matrix):
    num_return = 1
    neighbors = deque([(row, col)])
    while neighbors:
      row, col = neighbors.popleft()
      if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
        continue
 
Rishabh Shukla

Rishabh Shukla

· 2 years ago

from collections import deque

class Solution:
  def countClosedIslands(self, matrix):
    countClosedIslands = 0
    
    self.n = len(matrix)
    self.m = len(matrix[0])

    self.matrix = matrix

    self.visited = [[False for y in range(self.m)] for x in range(self.n)]

    for i in range(self.n):
      for j in range(self.m):
        if self.matrix[i][j] == 1 and not self.visited[i][j]:
          is_closed = self.bfs(i, j)
          if is_closed:
            countClosedIslands += 1

    return countClosedIslands

  def bfs(self, p, q):
    queue = deque([(p, q)])

    closed = True

    while queue:
      row, col = queue.popleft()

      if row < 0 or row >= self.n or col < 0 or col >= self.m:
        closed = False
        continue

      if self.matrix[row][col] == 0: