Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Solution: Problem Challenge 1

The problem statement is incorrect based on the test cases.

Some Dude · 2023-07-27T22:39:48.353Z

The description states: "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)." Based on this definition, an island of [[1]] should not be an island, since it's not a set of connected 1s. Ignoring that and pretending a single 1 is an island, the below test case has multiple singular islands, which violates the following: "The given matrix has only one island, write a function to find the perimeter of that island." [[0,1,0,1,0,1,0,1,0],[1,0,1,0,1,0,1,0,1],[0,1,0,1,0,1,0,1,0]] So what's actually the expected behaviour here??

Problem Statement

You are given a 2D matrix (a grid) where every cell holds either 1 for land or 0 for water. Cells connect horizontally and vertically, never diagonally.

An island is a group of connected land cells, and the water around it reaches the edge of the matrix. Every cell is a square with sides of length 1.

The island may contain a lake, which is water fully enclosed by land. The wall around a lake is part of the island's boundary, so it counts toward the perimeter exactly as the outer edge does.

The matrix holds at most one island

.....

Like the course? Get enrolled and start learning!

Mallory

· 21 hours ago

Show 1 reply

Michael Shum

· 4 months ago

Something is off - I'm running this with essentially the solution:

class Solution {
  findIslandPerimeter(matrix) {
    // TODO: Write your code here
    // dfs 
    const nRows = matrix.length, nCols = matrix[0].length;
    const visited = new Array(nRows).fill(false).map(() => new Array(nCols).fill(false));
    
    for (let row = 0; row < nRows; row++) {
      for (let col = 0; col < nCols; col++) {
        if (matrix[row][col] === 1) {
          // for each cell, check if === 1 and not visited, and do dfs
          return this.dfs(row, col, matrix, visited);
        }
      }
    }
  }

  // for each dfs
  dfs(row, col, matrix, visited) {
    // each cell should return its perimeter

    // base case:
    // out of bounds - return 1
    if (!(0 <= row && row < matrix.le

Show 1 reply

edisonfreire14

· a year ago

Key intuition:

If there is a island block (a 1 in the matrix) the perimeter of that singular block is 4 - the number of other island blocks it is connected to.

So if you go to every island block and check the 4 directions from it count out of the sides are connected then subtract that from 4 we know the perimeter of that block.

So if you do that for every island block and sum it up it will give you the perimeter for the island in the matrix. This in theory would work to find perimeter of multiple islands, if they had lakes too.

def findIslandPerimeter(self, matrix):
    # TODO: Write your code here
    rows = len(matrix)
    cols = len(matrix[0])
    deltas = [(1,0),(-1,0),(0,1),(0,-1)]
    def check_around(i,j):
      connected = 0
      for i_delta, j_delta in deltas:

Show 1 reply

Hugh Parry

· 2 years ago

Boy I hope that the hiring manager at aws will like this

class Solution:
    def findIslandPerimeter(self, m):
        return sum(sum(4 - (i > 0 and m[i-1][j]) * 2 - (j > 0 and m[i][j-1]) * 2 for j in range(len(m[0])) if m[i][j]) for i in range(len(m)))

Show 1 reply

siddhantgawsane

· 2 years ago

I have a much simpler solution by simply counting the number of 0 edges

class Solution:
  def findIslandPerimeter(self, matrix):
    # TODO: Write your code here
    perimeter = 0
    for i, column in enumerate(matrix):
      for j, elem in enumerate(column):
        if elem == 1:
          if 0 > i-1 or matrix[i-1][j] == 0:
            perimeter += 1
          if i+1 > len(matrix)-1 or matrix[i+1][j] == 0:
            perimeter += 1
          if 0 > j-1 or matrix[i][j-1] == 0:
            perimeter += 1
          if j+1 > len(column)-1 or matrix[i][j+1] == 0:
            perimeter += 1                                

    return perimeter

Show 1 reply

lejafilip

· 2 years ago

Show 1 reply

Mohammed Dh Abbas

· 2 years ago

class Solution:
  
  def get_neighbors(self, matrix, i, j):
    neighbors = []
    rows = [-1, 0, 1, 0]
    cols = [0, 1, 0, -1]
    for k in range(len(rows)):
      x = rows[k] + i
      y = cols[k] + j
      if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix[0]):
        neighbors.append((x, y))
    return neighbors
  
  def cacl_perimeter(self, matrix, i, j):
    perimeter = 0
    # top perimeter
    if  i == 0 or (i - 1 >= 0 and matrix[i - 1][j] == 0):
      perimeter += 1
    # bottom perimeter  
    if  i == len(matrix) - 1 or (i + 1 < len(matrix) and matrix[i + 1][j] == 0):
      perimeter += 1
    # left perimeter
    if  j == 0 or (j - 1 >= 0 and matrix[i][j - 1] == 0):
      perimeter += 1
    # right perimeter  
    if  j == len(matrix[0]) - 1 or (j + 1 <

Semih kekül

· 3 years ago

# the total should be returned not just the edge of a single island
# correct implementation is below

def findIslandPerimeter(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    visited = [[False for i in range(cols)] for j in range(rows)]
    total = 0 # added
    for i in range(rows):
        for j in range(cols):
            if (matrix[i][j] == 1 and not visited[i][j]):
                total += islandPerimeterDFS(matrix, visited, i, j) # updated

    return total # updated

Show 1 reply

Mikhail Putilov

· 3 years ago

Show 1 reply

Some Dude

· 3 years ago

Show 2 replies

Reading Progress

Vote for new content