Leetcode 463. Island Perimeter

Problem

Leetcode 463 - Island Perimeter

Example:

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

Input: grid = [[1]]
Output: 4

Input: grid = [[1,0]]
Output: 4

Approach

We can check every single grid then we can check its top, right, left, and bottom to see if grid exists in that area. If it does, then we don’t increment the res, else we increment.

Here is the Python code for the solution:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    if (i-1 >= 0 and grid[i-1][j]== 0) or i-1 < 0:
                        res += 1
                    if (i+1 < len(grid) and grid[i+1][j] == 0) or i+1 >= len(grid):
                        res += 1
                    if (j-1 >= 0 and grid[i][j-1] == 0) or j-1 < 0:
                        res += 1
                    if (j+1 < len(grid[0]) and grid[i][j+1] == 0) or j+1 >= len(grid[0]):
                        res += 1
        
        return res        

Time Complexity and Space Complexity

Time Complexity: $O(n * m)$ where $m$ is length of columns of grid $n$ is length of rows of grid

Space Complexity: $O(1)$