Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Number of Islands

Medium
graphbfsdfsmatrixunion-find

Given an r × c grid of 1 (land) and 0 (water), count the islands — groups of land connected horizontally or vertically.

Input

  • Line 1: two integers r c
  • Next r lines: the grid rows (space-separated 0/1)

Output: the number of islands.

Example 1
Input:
4 5
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0
Output:
1
Example 2
Input:
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Output:
3

Constraints

  • 1 ≤ r, c ≤ 300
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.