Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 2

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

Two islands are considered the same if and only if they can be translated (not rotated or reflected) to equal each other.

Write a function to find the number of distinct islands in the given matrix.

Example 1

Input: matrix =

Output: 2

.....

.....

.....

Like the course? Get enrolled and start learning!
D

Dhruba Jyoti Nath

· 4 years ago

islandTraversal += "B"; // back why is this necessary?

Show 2 replies
D

Dhruba Jyoti Nath

· 4 years ago

islandTraversal += "B"; // back why is this necessary?

Show 1 reply
V

Victor An

· 4 years ago

Share a BFS version


from typing import List
from collections import deque


class Solution:

def numDistinctIslands(self, grid: List[List[int]]) -> int:
self.rows = len(grid)
self.cols = len(grid[0])
self.directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

island_pattern_set = set()

for x in range(self.rows):
for y in range(self.cols):
if grid[x][y] ==  1:
island_pattern = self.getIslandPattern(grid, x, y)
island_pattern_set.add(tuple(island_pattern))

return len(island_pattern_set)

def getIslandPattern(self, grid, ox, oy):
# BFS
island_pattern = list()
neighbors = deque()
neighbors.append((ox, oy))
while neighbors:
x, y = neighbors.popleft()
# add relative position to the pattern
island_pattern.append((x - ox, y - oy))
grid[x][y] = 0 # mark visited
for ix, iy in self.directions:
nx,
C

CaptainKidd

· 4 years ago

Much like one of the earlier questions. A matrix isn't required to keep track of where you have been. Just set the grid value to something not used like 2 and add an extra if check inside the recursive call for DFS to save memory.

Show 1 reply
S

shukl034

· 3 years ago

Trying to think of scenarios where the B append could make the difference

Show 1 reply
L

Lee

· 2 years ago

    def findDistinctIslandsBit(self, matrix):
        if not matrix or not matrix[0]:
            return None
        # iterate over the matrix finding islands
        # dfs the island shifting the islands "code" based on the traversal
        # add the code int to a set, then return the size of the set
        # will use explicit stack dfs (for no particular reason)
        def dfsIsland(rowStart, colStart):
            code = 0
            stack = [(rowStart, colStart)]
            while stack:
                i, j = stack.pop()
                code <<= 1
                if not (0 <= i < n) or not (0 <= j < m):
                    continue
                code += matrix[i][j]
                if matrix[i][j]:
                    for diff in [-1, 1]:
                        s
S

Silencer312

· 2 years ago

The problem is very similar and often asked as a follow up to this problem in interviews

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  
  def get_neigbors(self, matrix, i, j):
    neigbors = []
    up = (-1, 0, 'u')
    right = (0, 1, 'r')
    down = (1, 0, 'd')
    left = (0, -1, 'l')
    alpha = [up, right, down, left]
    for x, y, _dir in alpha:
      row = i + x
      col = j + y
      if row >= 0 and row < len(matrix) and col >= 0 and col < len(matrix[0]) and matrix[row][col] == 1:
        neigbors.append((row, col, _dir))
    return neigbors

  def dfs(self, matrix, i, j, path, all_paths, _dir):    
    if matrix[i][j] == 0:
      return 

    stack = [(i, j, _dir)]
    matrix[i][j] = 0 
    
    while stack:
      x, y, _dir = stack.pop()
      path.append(_dir)
      for row, col, direction in self.get_neigbors(matrix, x, y):
        stack.append((row, col, direction))
        matr
K

kfaham

· a year ago

class Solution:
  def findDistinctIslandsDFS(self, matrix):
    sizes = set()

    def size(i, j):
      if not (0 <= i < len(matrix) and 0 <= j < len(matrix[0])) or matrix[i][j] == 0:
        return 0
      matrix[i][j] = 0
      return size(i + 1, j) + size(i - 1, j) + size(i, j + 1) + size(i, j - 1) + 1
    
    for i in range(len(matrix)):
      for j in range(len(matrix[i])):
        if matrix[i][j] == 1:
          sizes.add(size(i, j))

    return len(sizes)
Quốc Phong Trần

Quốc Phong Trần

· a month ago

class Solution:
  def findDistinctIslandsDFS(self, matrix):
    # TODO: Write your code here
    row = len(matrix)
    col = len(matrix[0])
    visited = [[False for i in range(col)] for j in range(row)]
    m = {}
    def dfs(x, y):
      if x < 0 or x >= row or y < 0 or y >= col:
        return 1
      if visited[x][y]:
        return 0
      if matrix[x][y] == 0:
        return 1
      visited[x][y] = True
      peri = 0
      peri += dfs(x + 1, y)
      peri += dfs(x - 1, y)
      peri += dfs(x, y + 1)
      peri += dfs(x, y - 1)
      return peri
    numberOfIsland = 0
    for i in range(row):
      for j in range(col):
        if not visited[i][j] and matrix[i][j] == 1:
          peri = dfs(i, j)
          if peri not in m:
            m[peri] = 1
            numberOfIsland