Island Perimeter Leetcode Solution

Table of Contents

Problem Statement

In this problem, we are given a grid in form of a 2-D array. grid[i][j] = 0 represents there is water at that point and grid[i][j] = 1 represents land. Grid cells are connected vertically/horizontally but not diagonally. There is exactly one island (a connected component of land cells) in the given input. We need to determine the perimeter of this problem.

Example

grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}}

grid = {{1}}

Approach (Simple Counting)

The simple way to see the problem is that only the land cells will contribute to the parameter. A land cell that has any side which is unshared with any other land cell can be taken into account in order to calculate the perimeter. It is because if a land cell shares some side with any other land cell, that will not be the outer boundary of the island in the grid.

Implementation of Island Perimeter Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size();
    int perimeter = 0 , sides = 0;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m;  j++) {
            if(grid[i][j] == 1) {
                sides = 0;
                if(i == 0)
                    sides++;
                else
                    sides += (grid[i - 1][j] == 0);

                if(j == 0)
                    sides++;
                else
                    sides += (grid[i][j - 1] == 0);

                if(i == n - 1)
                    sides++;
                else
                    sides += (grid[i + 1][j] == 0);

                if(j == m - 1)
                    sides++;
                else
                    sides += (grid[i][j + 1] == 0);

                perimeter += sides;
            }
        }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

Java Program

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length;
        int perimeter = 0 , sides = 0;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m;  j++) {
                if(grid[i][j] == 1) {
                    sides = 0;
                    if(i == 0)
                        sides++;
                    else if(grid[i - 1][j] == 0)
                        sides++;

                    if(j == 0)
                        sides++;
                    else if(grid[i][j - 1] == 0)
                        sides++;

                    if(i == n - 1)
                        sides++;
                    else if(grid[i + 1][j] == 0)
                        sides++;

                    if(j == m - 1)
                        sides++;
                    else if(grid[i][j + 1] == 0)
                        sides++;

                    perimeter += sides;
                }
            }
        return perimeter;
    }
}

Complexity Analysis of Island Perimeter Leetcode Solution

Time Complexity

O(N * M) where N = number of rows in the grid, M = number of columns in the grid.

Space Complexity

O(1) as we use constant space for variables.

Approach (Effective Counting)

In the above approach, we were counting the sides of a land cell that contributes to the perimeter by checking its four neighbors. We can improve that to just checking two neighbors. As we right and down in the grid to traverse it, we can only keep a check of left and up cells to a land cell. We can assume that every land cell contributes ‘4’ to the perimeter of the island. But if a land cell shares its side(s) with any other cell, we will subtract 2 from it(one for its shared side and one as the other cell shares a side too). The time complexity of both the solutions is the same but we somewhat improve on grounds of operation in this approach.