Island Perimeter

Island Perimeter

Companies: Amazon, Facebook, Google

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

Input:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Output: 16

Explanation: It is given that the cell which represents 1 is the square block of side length 1 unit. The figure joining all the cells representing 1 has perimeter equal to 16 in this example.

Solution:

Every cell has perimeter of 4 unit. All the cells representing 1 have perimeter equal to 4. So, summing up all these cells will be give us total perimeter but we need to take care about the cells which are joined together as their sides will overlap each other and we have to reduce the total perimeter by that side length. So, everytime, we increment the count by 4 whenever we encounter the island.

Checking from the current island towards two directions, one towards left and other towards top. If we see any neighbours islands, we will deduct the overlapped side lengths from the perimater count.

Implementation:

Java:

class Solution {
    public int islandPerimeter(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    count += 4;
                    if (i > 0 && grid[i - 1][j] == 1) {
                        count -= 2;
                    }
                    if (j > 0 && grid[i][j - 1] == 1) {
                        count -= 2;
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis:

• Time Complexity: O(n²)

• Space Complexity: O(1).