Frontend School

Special Island Perimeters

DSA
medium

Special Island Perimeters

Medium
Matrix
BFS
DFS
Graph

Overview

In surveying and resource management applications, accurately calculating land area and perimeters is crucial. Imagine a scenario where you're analyzing geographical data represented as a grid, where different cell types signify water, normal land, or 'special' resource-rich land. These special land areas, while connected to normal land, might have unique properties that affect their perimeter contribution, perhaps due to environmental sensitivities or higher-value resources.

Your task is to implement a system that can precisely measure the total perimeter of all 'islands' in such a grid, taking into account these special land types and their unique perimeter contributions.

What you need to do / Task

Implement the function calculateSpecialIslandPerimeters that takes a 2D grid of integers and returns the total perimeter of all islands within it. An island is formed by connected 1s (normal land) and 2s (special land) in horizontal or vertical directions.

Your function must adhere to the following rules:

  1. Connectivity: Land cells (1 or 2) are connected if they are horizontally or vertically adjacent.
  2. Perimeter Definition: The perimeter is calculated by summing the lengths of all edges of land cells that are adjacent to a water cell (0) or are at the grid boundary.
  3. Special Cell Contribution:
    • A normal land cell (1) contributes 1 unit to the perimeter for each adjacent water cell (0) or grid boundary.
    • A special land cell (2) contributes 2 units to the perimeter for each adjacent water cell (0) or grid boundary.

Input & output

  • Input:

    • grid: A number[][] representing the map. Each cell contains 0 (water), 1 (normal land), or 2 (special land).
  • Output:

    • A number representing the total perimeter of all islands in the grid.

Clarifications

  • Grid Boundaries: Cells outside the grid boundaries are considered water (0).
  • Diagonal Connections: Diagonal connections do not count as land connections. Only horizontal and vertical adjacency forms an island.
  • Empty Grid: If the input grid is empty or has empty rows, the total perimeter is 0.

Examples

1

Example 1

Input:

grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0]]

Output:

12

Note:

This grid forms a single island. Each '1' cell contributes 1 unit for each adjacent water cell (0) or grid boundary.

  • Cell (0,1): 3 water/boundary neighbors (top boundary, (0,0), (0,2)). Perimeter: 3.
  • Cell (1,0): 3 water/boundary neighbors (left boundary, (0,0), (2,0)). Perimeter: 3.
  • Cell (1,1): 0 water/boundary neighbors (all are land).
  • Cell (1,2): 3 water/boundary neighbors (right boundary, (0,2), (2,2)). Perimeter: 3.
  • Cell (2,1): 3 water/boundary neighbors (bottom boundary, (2,0), (2,2)). Perimeter: 3. Total = 3 + 3 + 0 + 3 + 3 = 12.
2

Example 2

Input:

grid = [[0,1,0,0],[1,2,1,0],[0,1,0,0]]

Output:

12

Note:

This is similar to the first example but with a '2' cell at (1,1).

  • Cell (0,1) [1]: 3 water/boundary neighbors. Perimeter: 3 * 1 = 3.
  • Cell (1,0) [1]: 3 water/boundary neighbors. Perimeter: 3 * 1 = 3.
  • Cell (1,1) [2]: 0 water/boundary neighbors (all adjacent cells are land). Perimeter: 0 * 2 = 0.
  • Cell (1,2) [1]: 3 water/boundary neighbors. Perimeter: 3 * 1 = 3.
  • Cell (2,1) [1]: 3 water/boundary neighbors. Perimeter: 3 * 1 = 3. Total = 3 + 3 + 0 + 3 + 3 = 12.
3

Example 3

Input:

grid = [[1,0,0,1],[0,0,0,0],[1,0,2,0]]

Output:

20

Note:

This grid has four separate islands:

  • Island 1 (cell (0,0) [1]): 4 water/boundary neighbors. Perimeter: 4 * 1 = 4.
  • Island 2 (cell (0,3) [1]): 4 water/boundary neighbors. Perimeter: 4 * 1 = 4.
  • Island 3 (cell (2,0) [1]): 4 water/boundary neighbors. Perimeter: 4 * 1 = 4.
  • Island 4 (cell (2,2) [2]): 4 water/boundary neighbors. Perimeter: 4 * 2 = 8. Total = 4 + 4 + 4 + 8 = 20.

Constraints

Constraints & assumptions

  • 1 <= grid.length, grid[0].length <= 100
  • grid[i][j] will be 0, 1, or 2.
  • The grid is guaranteed to be rectangular (i.e., grid[i].length is consistent for all i).

Out of scope

  • Input validation for non-integer values or incorrect grid dimensions (assume valid input based on constraints).
  • Optimizing for extremely sparse or dense grids beyond standard graph traversal efficiency.

What interviewers evaluate

  • Correctness: Accurately calculates the total perimeter based on specified rules for both 1 and 2 cells.
  • Algorithm Efficiency: Employs an efficient graph traversal algorithm (e.g., BFS or DFS) to process the grid and avoid redundant computations.
  • Edge Case Handling: Correctly handles grid boundaries, isolated cells, and scenarios with no islands.
  • Code Quality: Demonstrates clean, readable, and well-structured code with appropriate variable naming.

Loading editor...