algoadvance

Leetcode 463. Island Perimeter

Problem Statement

You are given a grid of size m x n representing a map where 1 represents land and 0 represents water. The 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).

Return the perimeter of the island.

Example 1:

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

Example 2:

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

Example 3:

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

Clarifying Questions

  1. Input Constraints: Can you confirm that the grid will always have at least one land cell?
    • Yes, the problem states that there is exactly one island.
  2. Largest Grid Size: Are there constraints on how large the grid can be?
    • Typically, constraints are mentioned in the problem, for this problem often m and n can go up to 100, so we should aim for an efficient solution.

Strategy

To determine the perimeter of the island:

  1. Traverse each cell in the grid.
  2. If the cell contains land (1), increase the perimeter by 4 (since an isolated land cell contributes 4 to the perimeter).
  3. For each land cell, check its neighbors (left, right, top, bottom). If a neighboring cell is also land, reduce the perimeter for each shared edge (since shared edges do not count towards the perimeter).

Code

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    perimeter += 4;
                    
                    // Check top neighbor
                    if (r > 0 && grid[r - 1][c] == 1) perimeter -= 2;
                    // Check left neighbor
                    if (c > 0 && grid[r][c - 1] == 1) perimeter -= 2;
                }
            }
        }
        
        return perimeter;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] test1 = // use example above
                         {1, 1, 1, 0}, 
                         {0, 1, 0, 0}, 
                         {1, 1, 0, 0}};
        System.out.println(solution.islandPerimeter(test1)); // Output: 16

        int[][] test2 = // use example above
        System.out.println(solution.islandPerimeter(test2)); // Output: 4

        int[][] test3 = // use example above
        System.out.println(solution.islandPerimeter(test3)); // Output: 4
    }
}

Time Complexity

The time complexity of this solution is O(m * n) where m is the number of rows and n is the number of columns in the grid. This is because we are traversing each cell in the grid exactly once and performing a constant amount of work for each cell.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI