algoadvance

Leetcode 463. Island Perimeter

Problem Statement

We are given a 2D grid, grid, which is a representation of a map where:

Grid cells are connected horizontally or 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,” meaning the water inside the island doesn’t connect to the water outside the island.

We need to return the perimeter of the island.

Clarifying Questions

  1. Shape and Size of the Grid: Is there any constraint on the size of the grid?
    • Typically, constraints are given in the problem statement. For this problem, we can assume the grid dimensions are within reasonable bounds (e.g., 1 ≤ grid.length, grid[0].length ≤ 100).
  2. Multiple Islands: Can there be multiple islands?
    • No, the problem explicitly states there is exactly one island.
  3. Types of Connections: Are cells connected only horizontally and vertically?
    • Yes, only horizontal and vertical connections are considered.
  4. Edge Cases:
    • Minimal grid size with no land.
    • A grid with land cells forming various shapes.

Strategy

To calculate the perimeter, we can iterate through each cell in the grid:

Steps:

  1. Initialize perimeter to 0.
  2. Traverse each cell in the grid.
  3. For each land cell:
    • Add 4 to the perimeter.
    • Check for adjacent land cells to the right and below, and subtract 1 for each to account for shared edges.

Code

#include <vector>

class Solution {
public:
    int islandPerimeter(std::vector<std::vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        int perimeter = 0;

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == 1) {
                    // Assume all four sides contribute to the perimeter initially
                    perimeter += 4;

                    // Check the cell to the right
                    if (j < cols - 1 && grid[i][j + 1] == 1) {
                        // Subtract 2 since both cells contribute only 1 total to perimeter between them
                        perimeter -= 2;
                    }
                    // Check the cell below
                    if (i < rows - 1 && grid[i + 1][j] == 1) {
                        // Subtract 2 for the same reason
                        perimeter -= 2;
                    }
                }
            }
        }
        return perimeter;
    }
};

Time Complexity

The time complexity of this solution is O(n*m), where n is the number of rows and m is the number of columns in the grid. Each cell is visited once, making this approach efficient for the problem constraints.

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