Bounding Coordinates of Rectangular Regions
Intuit● MediumNEW GRADOAProblem statement
A binary matrix image contains foreground cells equal to foregroundValue; the other value is background. Every maximal side-connected foreground region is a completely filled axis-aligned rectangle. Different rectangles never share a side. They may touch diagonally.
Return one row [top, left, bottom, right] for every region, using zero-based inclusive coordinates. A single foreground cell is a valid rectangle. Return maximal regions only, without also returning their smaller subrectangles.
For this exercise, assume foregroundValue is an explicit input, either 0 or 1, so both reported foreground conventions are supported. Return rectangles in row-major order of their top-left corners. If no foreground cell exists, return an empty array.
Function
getRectangleCoordinates(image: int[][], foregroundValue: int) → int[][]Examples
Example 1
image = [[1,1,1,1,1,1],[0,0,1,0,1,1],[0,0,1,0,1,0],[1,1,1,0,1,0],[1,0,0,1,1,1]]foregroundValue = 0return = [[1,0,2,1],[1,3,3,3],[2,5,3,5],[4,1,4,2]]There are four zero-valued regions. Their inclusive bounds are [1,0,2,1], [1,3,3,3], [2,5,3,5], and [4,1,4,2]. The last region touches another region diagonally but remains separate.
Example 2
image = [[0,0,0,0,0,0],[0,0,1,1,0,0],[0,0,1,1,0,0],[0,1,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0]]foregroundValue = 1return = [[1,2,2,3],[3,1,4,1]]The first one-valued rectangle spans rows 1 through 2 and columns 2 through 3. The second spans rows 3 through 4 in column 1. Their diagonal contact does not join them.
Constraints
- For this exercise, assume
1 <= image.length <= 50and every row has the same length from 1 to 50. - Every cell is 0 or 1, and
0 <= foregroundValue <= 1. - Each maximal component connected by up, down, left, or right moves is a filled rectangle. Distinct rectangles may touch only at corners.