FunctionRacerProblemsRace

Rectangular Islands

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

grid [[1,1,0,1],[1,1,0,1],[0,0,0,0],[1,1,1,0]]
returns 3

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

grid [[1,1,0],[1,0,0],[0,0,1]]
returns 1

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems