Ctrl K

Rectangular Fields on a Map

Medium
A land plot is described by a grid plan of zeros and ones: 1 is farmland and 0 is forest. The farmland forms separate fields, and every field is a solid rectangle. Two different fields never share a side: there is always forest between them (touching diagonally is possible). For each field return [r1, c1, r2, c2], where (r1, c1) is the row and column of its top-left cell and (r2, c2) of its bottom-right cell (0-based). The fields may be listed in any order. If there is no farmland, return an empty list.
Example 1
plan=[[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 0, 1]] → [[0, 0, 1, 1], [0, 3, 0, 3], [2, 3, 2, 3]]

Three fields: a 2×2 square with corners (0, 0) and (1, 1), plus two single-cell fields at (0, 3) and (2, 3).

Example 2
plan=[[0, 1, 1, 1]] → [[0, 1, 0, 3]]

One field in row 0, from column 1 to column 3.

Example 3
plan=[[0, 0], [0, 0]] → []

All forest, no fields.

Constraints
  • 1 ≤ len(plan), len(plan[0]) ≤ 300
  • every cell is 0 or 1
  • every field is a solid rectangle and no two fields share a side
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsDrain the Landlocked Ponds MediumLand Regions on a Map MediumRain Reaching Both Seas MediumCan the Ball Stop at the Target MediumShortest Path of a Rolling Ball Medium
loading Python…
Input
plan=[[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 0, 1]]
Expected
[[0, 0, 1, 1], [0, 3, 0, 3], [2, 3, 2, 3]]

Run checks the first 3 tests in your browser. Submit checks all 49 tests on the server, hidden ones included.