Interview Question Island Perimeter

By Fatih KABAKCI

The problem is to calculate perimeter of an island which is being represented as two dimensional array that its cells refer LAND with 1 - length square cell if the value of cell is 1. 0 represents water in island.

Problem #463 - Island Perimeter

Description: 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:

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

Difficulty: Easy

Solution in Java

package com.fatihkabakci.Easy.IslandPerimeter;

/**
 * @author fkabakci
 * Problem Description: 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:
 * 
 * [[0,1,0,0],
 * [1,1,1,0],
 * [0,1,0,0],
 * [1,1,0,0]]
 * 
 * Answer: 16
 * Explanation: The perimeter is the 16 yellow stripes in the image below:
 * 
 * Solution:
 * 1. Traverse island.
 * 2. If encountered a land, then look at your left, right, up, and down.
 *       then increase perimeter 4.
 * 3. If there is another neighbor land,
 * 		 then decrease perimeter 1.
 */
public class Solution {
	final static int LAND = 1;
	
	public int islandPerimeter(int[][] grid) {
		int perimeter = 0;
		
		final int ROW = grid.length;
		for(int i = 0; i < ROW; i++) {
			final int COLUMN = grid[i].length;
			for(int j = 0; j < COLUMN; j++) {
				final int LEFT = j - 1;
				final int RIGHT = j + 1;
				final int UP = i - 1;
				final int DOWN = i + 1;
		
				if (grid[i][j] == LAND) {
					if (LEFT > -1 && grid[i][LEFT] == LAND)
						perimeter -= 1;
					if (RIGHT < COLUMN && grid[i][RIGHT] == LAND)
						perimeter -= 1;
					if (UP > -1 && grid[UP][j] == LAND)
						perimeter -= 1;
					if (DOWN < ROW && grid[DOWN][j] == LAND)
						perimeter -= 1;

					perimeter += 4;
				}
			}
		}
        return perimeter;
    }
	
	public static void main(String[] args) {
		int perimeter = new Solution().islandPerimeter(new int[][] { { 0, 1, 0, 0 },
				{ 1, 1, 1, 0 }, { 0, 1, 0, 0 }, { 1, 1, 0, 0 } });
		System.out.println(perimeter);
	}
}

Do we really need to look up at LEFT and UP as well ?

Theoretically no. Because two adjacent node has already shared two sides. If we hold islands and neighbours at the same time by looking only right and bottom, we can define that perimeter is 4 * islands - 2 * neighbours since each island has 4 sides, and every adjacent side has 2 common sides. However, writing a code block that has included all directions might be more intuitive to understand easily.