515. Smallest Rectangle Enclosing Black Pixels

Given a binary image where 1 represents a black pixel and 0 a white one, with all black pixels forming a single connected region, and given the coordinates (x, y) of one black pixel, return the area of the smallest axis-aligned rectangle that encloses all black pixels. The input is JSON {image, x, y}. Use binary search to find the boundary rows and columns.

Input: JSON {image, x, y}.

Output: Integer — the smallest enclosing rectangle area.

Examples

Input: {"image":[[0,0,1,0],[0,1,1,0],[0,1,0,0]],"x":0,"y":2}
Output: 6
Explanation: Rows 0-2, cols 1-2: area 3*2=6.

Input: {"image":[[1]],"x":0,"y":0}
Output: 1
Explanation: Single black pixel.

Input: {"image":[[0,1],[1,1]],"x":1,"y":1}
Output: 4
Explanation: Bounding box is 2x2.

Constraints

• 1<=rows,cols<=100
• at least one black pixel

Asked by