Rectangular Islands
grid is a rectangular grid of 0 (water) and 1 (land) given as a list of rows. An island is a largest possible group of land cells in which every cell can reach every other by moving up, down, left or right through land; diagonal neighbours do not connect.
An island is rectangular when its cells fill a whole rectangle: take the smallest and largest row and the smallest and largest column among its cells; every cell inside that range must belong to the island. A single land cell is a rectangular island. Return the number of rectangular islands; return 0 when there is no land.
Example 1
The 2 by 2 block, the column of two cells on the right and the row of three cells at the bottom are all rectangles.
Example 2
The three cells at the top left form an L shape, whose bounding rectangle has an empty corner; the lone cell at the bottom right is a 1 by 1 rectangle.
Constraints
1 <= rows, cols <= 10- every cell is
0or1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Rounds of Parallel JobsMedium
- Sealed RoomsMedium
- Smallest Task OrderMedium
- Smallest Team SplitMedium
- Steps to the ExitMedium
- Through the CheckpointMedium
- Towns Within BudgetMedium
- Break Through WallsHard