Island Perimeter - Practice Coding Problems

Island Perimeter - Problem

You are given a row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 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", meaning the water inside 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.

Input & Output

Example 1 — Small Island

$ Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]

› Output: 16

💡 Note: The island has an irregular shape. Each land cell contributes edges that face water or boundaries. Total perimeter is 16.

Example 2 — Single Cell

$ Input: grid = [[1]]

› Output: 4

💡 Note: A single land cell has 4 edges, all facing the boundary (water), so perimeter is 4.

Example 3 — Square Island

$ Input: grid = [[1,1],[1,1]]

› Output: 8

💡 Note: A 2x2 square island. Each of the 4 cells contributes 2 edges to the perimeter (4×2=8).

Constraints

row, col ≤ 100
grid[i][j] is 0 or 1
There is exactly one island

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid where 1=land, 0=water

Find Perimeter

Count edges between land and water/boundary

Output Count

Total perimeter length

Key Takeaway

🎯 Key Insight: Count edges where land cells touch water or grid boundaries

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is that each land cell contributes 4 edges minus the number of adjacent land cells. The most intuitive approach is to check each land cell's 4 directions and count edges facing water or boundaries. Time: O(m×n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Count All Edges	O(m×n)	O(1)	For each land cell, count edges that don't have adjacent land cells
Smart Edge Counting	O(m×n)	O(1)	Count 4 edges per land cell, then subtract 2 for each adjacent land pair
DFS Traversal	O(m×n)	O(m×n)	Use DFS to traverse the island and count perimeter edges during exploration

Count All Edges — Algorithm Steps

Step 1: Iterate through each cell in the grid
Step 2: For each land cell (value = 1), check all 4 adjacent positions
Step 3: Count edges where adjacent cell is water (0) or out of bounds
Step 4: Return total count of perimeter edges

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Land Cell

Locate a cell with value 1

Check 4 Directions

Count edges facing water/boundary

Sum All Edges

Total perimeter count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int rows = gridSize, cols = gridColSize[0];
    int perimeter = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                // Check all 4 directions
                // Up
                if (i == 0 || grid[i-1][j] == 0) perimeter++;
                // Down
                if (i == rows-1 || grid[i+1][j] == 0) perimeter++;
                // Left
                if (j == 0 || grid[i][j-1] == 0) perimeter++;
                // Right
                if (j == cols-1 || grid[i][j+1] == 0) perimeter++;
            }
        }
    }
    
    return perimeter;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids
    int grid[100][100];
    int rows = 0, cols = 0;
    
    // Count rows by counting '],'
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            if (rows == 0) {
                // Count columns in first row
                char* temp = ptr + 1;
                cols = 1;
                while (*temp && *temp != ']') {
                    if (*temp == ',') cols++;
                    temp++;
                }
            }
            
            // Parse row
            ptr++; // Skip '['
            for (int j = 0; j < cols; j++) {
                while (*ptr && (*ptr == ' ' || *ptr == ',')) ptr++;
                grid[rows][j] = *ptr - '0';
                ptr++;
            }
            rows++;
        }
        ptr++;
    }
    
    // Create array of pointers for solution function
    int* gridPtrs[100];
    int colSizes[100];
    for (int i = 0; i < rows; i++) {
        gridPtrs[i] = grid[i];
        colSizes[i] = cols;
    }
    
    int result = solution(gridPtrs, rows, colSizes);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Visit every cell in the m×n grid once

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra variables

✓ Linear Space

285.0K Views

Medium Frequency

~15 min Avg. Time

4.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Count All Edges — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler