Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
O(m*n)
, m being the rows of matrix and n being the columns of matrix. Space complexity should be O(1)
, excluding the recursive stack.HAPPY CASE
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image below.
Input: grid = [[1,0]]
Output: 4
EDGE CASE
Input: grid = [[1]]
Output: 4
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For 2D-Array, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Perform a DFS on the island in the grid and recursively we can count every piece of land's perimeter. If it is either a boarder or water return 1. If land was accounted for return 0. If it's unaccounted land, then recursively return perimeter of it's neighbors.
main function:
1) Iterate over the grid
2) If a '1' is seen then "explore" the island from this '1' using dfs and return parameter
dfs function:
1) Basecase 1: for out of bound items, return 1, because the boundary of the square suggest perimeter
2) Basecase 2: for water, return 1, because this side is a perimeter
3) Basecase 3: for '-1' return 0, because we have been there, this is land that we have accounted for
4) Change the grid value to '-1' to mark it as visited and recursively return the perimeter of neighbors to total perimeter of all neighbors.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int) -> int:
# Basecase 1: for out of bound items, return 1, because the boundary of the square suggest perimeter
if i < 0 or i > len(grid)-1 or j < 0 or j > len(grid[i])-1:
return 1
# Basecase 2: for water, return 1, because this side is a perimeter
elif grid[i][j] == 0:
return 1
# Basecase 3: for '-1' return 0, because we have been there, this is land that we have accounted for
elif grid[i][j] == -1:
return 0
# Change the grid value to '-1' to mark it as visited and recursively return the perimeter of neighbors to get perimeter of all neighbors.
else:
grid[i][j] = -1
return dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
# Iterate over the grid
for i in range(len(grid)):
for j in range(len(grid[i])):
# If a '1' is seen then "explore" the island from this '1' using dfs return perimeter
if grid[i][j] == 1:
return dfs(i, j)
public class Solution {
public int islandPerimeter(int[][] grid) {
// Iterate over the grid
if (grid == null) return 0;
for (int i = 0 ; i < grid.length ; i++){
for (int j = 0 ; j < grid[0].length ; j++){
// If a '1' is seen then "explore" the island from this '1' using dfs return perimeter
if (grid[i][j] == 1) {
return getPerimeter(grid,i,j);
}
}
}
return 0;
}
public int getPerimeter(int[][] grid, int i, int j){
// Basecase 1: for out of bound items, return 1, because the boundary of the square suggest perimeter
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {return 1;}
// Basecase 2: for water, return 1, because this side is a perimeter
if (grid[i][j] == 0) {
return 1;
}
// Basecase 3: for '-1' return 0, because we have been there, this is land that we have accounted for
if (grid[i][j] == -1) return 0;
// Change the grid value to '-1' to mark it as visited and recursively return the perimeter of neighbors to get perimeter of all neighbors.
grid[i][j] = -1;
return getPerimeter(grid, i-1, j) + getPerimeter(grid, i, j-1) + getPerimeter(grid, i, j+1) + getPerimeter(grid, i+1, j);
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of rows in 2D-array.
Assume M
represents the number of columns in 2D-array.