Island Perimeter

Island Perimeter is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

Problem statement

You are given a rectangular binary grid in grid. Each cell with value 1 is land, and each cell with value 0 is water. Cells are neighbors only when they share an edge; diagonal contact does not count. All land cells together form one island, meaning one edge-connected group of land cells.

The perimeter is the total number of land-cell edges that touch the outside boundary of the grid or a water cell. The island has no lakes, so there are no enclosed water regions inside it.

Implement islandPerimeter in the Solution class and return the island's perimeter as an integer.

Example 1:

Input: grid = [[0,1,0],[1,1,1],[0,1,0]] Output: 12 Explanation: The five land cells form a plus shape. Counting every side exposed to water or the grid boundary gives a perimeter of 12.

Example 2:

Input: grid = [[1,1,0,0],[0,1,1,0],[0,0,1,0]] Output: 12 Explanation: There are five land cells and four shared edges between neighboring land cells, so the perimeter is 5 × 4 - 2 × 4 = 12.

Example 3:

Input: grid = [[0,0,0],[0,1,0],[0,0,0]] Output: 4 Explanation: The single land cell has all four sides exposed to water, so the perimeter is 4.

Constraints:

- 1 <= grid.length <= 100 - 1 <= grid[0].length <= 100 - All rows in grid have the same length. - Each grid cell is either 0 or 1. - There is exactly one island, and all of its land cells are connected through shared edges. - The island has no lakes. - The grid contains at least one land cell.

Topics and companies

Topics: Array, Matrix, Graph, Counting.

How to practise Island Perimeter on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(R * C), where R is the number of rows and C is the number of columns. time and O(1) auxiliary space. space.

Open Island Perimeter in the code editor, or read the Island Perimeter editorial for a worked solution with its approach and complexity analysis.

Where Island Perimeter sits in the DSA pattern sheet

Problems related to Island Perimeter

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.