Count Islands

Given a grid representing a map with land and water, the task is to determine the number of distinct landmasses. This problem tests graph traversal skills, a fundamental concept in algorithm design and software engineering.

graphdfsmatrixrecursiongrid

Problem Statement

Imagine you have a digital elevation map represented as a two-dimensional array. Each cell in the array represents a location, and its value indicates whether it's part of a connected land area (represented by 1) or water (represented by 0). Your goal is to write a function that calculates the total number of separate, non-overlapping land regions in this map. Land regions are considered connected if they are adjacent either horizontally or vertically (not diagonally).

Example 1

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

Output: 2

The grid contains two separate land regions. One is in the top-left corner, and the other is in the bottom-right corner.

Example 2

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

Output: 1

The grid contains a single land region in the center.

Constraints

-The grid will only contain 0s and 1s.
-The grid will have at least one row and one column.
-The dimensions of the grid will be reasonable (e.g., not exceeding 500x500).
-The grid can be rectangular, not necessarily square.

Brute Force Approach

The brute-force approach would be like trying to count the number of distinct groups of friends at a party by going up to each person individually and asking if they're part of a group we haven't seen before. For each cell, you'd check its neighbors to see if they're land and part of a previously counted landmass. This involves iterating through the entire grid multiple times. The time complexity is O(mn(number of islands)), where m and n are the dimensions of the grid, and the space complexity is O(1) as it doesn't use extra space.

TimeO(m*n*k)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem