Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Problem Challenge 1

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

There are no lakes on the island, so the water inside the island is not connected to the water around it. A cell is a square with a side length of 1.

The given matrix has only one island, write a function to find the perimeter of that island.

Example 1

Input: matrix =

Output: 14

.....

.....

.....

Like the course? Get enrolled and start learning!
C

CaptainKidd

· 4 years ago

One small way to improve the answer provided in this challenge is doing away with the memory array to tell where you've been before. There's no need for it. Just mark the node as something other than 0 or 1 to mark that you've been there.

So for example mark the nodes you've visited with a value of 2 and then do a check grid[x][y] == 2 and if that's true you can return 0 in the recursive call. Saves a little time and memory.

Show 1 reply
Some Dude

Some Dude

· 3 years ago

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??

Show 2 replies
Semih kekül

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
Hugh Parry

Hugh Parry

· a year 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)))
A

Anthony DiFede

· 4 years ago

Could be missing edge cases, but it seems like the solution would be the number of land cells in the island * 2 + 2?

Show 1 reply
M

Mikhail Putilov

· 3 years ago

https://www.google.com/search?q=lake&oq=lake - A lake is a body of water that is surrounded by land.

I think the description has a typo: lakes are allowed. Designgurus has even a test case:

[

[0,0,0,0,0],

[0,1,1,1,0],

[0,1,0,1,0],

[0,1,1,1,0],

[0,0,0,0,0]

]

Show 1 reply
J

Jacob Song

· 4 years ago

Is this a typo? Shouldn't it be Island Perimeter instead of Parameter?

Show 4 replies
C

charles_hinson

· 3 years ago

I don't understand why the perimeter of this island [[1,1,1,1,0,1,1,1,1]] is 10 in the test case, shouldn't it be 20?

Show 1 reply
Mohammed Dh Abbas

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 <
L

lejafilip

· 2 years ago

[1,1,1,1,1,1,1,1,1,1],

[1,0,0,0,0,0,0,0,0,1],

[1,0,1,1,1,1,1,1,0,1],

[1,0,1,0,0,0,0,1,0,1],

[1,0,1,0,1,1,0,1,0,1],

[1,0,1,0,1,1,0,1,0,1],

[1,0,1,0,0,0,0,1,0,1],

[1,0,1,1,1,1,1,1,0,1],

[1,0,0,0,0,0,0,0,0,1],

[1,1,1,1,1,1,1,1,1,1]]

Every water in a island is a lake. Additionally we have several islands. They aren't mentioned in description. What should I do with them? Count or not?