# Find one rectangle

<https://leetcode.com/discuss/interview-question/437403/karat-interview-agent-phone-find-rectangle-coordinates>

> 1. there is an image filled with 0s and 1s. There is at most one rectangle in this image filled with 0s, find the rectangle. Output could be the coordinates of top-left and bottom-right elements of the rectangle, or top-left element, width and height.

\
Given a rectangle represented by a 0-1 2-d array and assume it contains one rectangle of all 0, return the upper left corner and lower right corner.\
Example:\
\[\[1,1,1,1,1],\
\[1,0,0,1,1],\
\[1,0,0,1,1],\
\[1,1,1,1,1]], you should return \[\[\[1,1],\[2,2]]]

Followup, what if there are multiple rectangles that are made of 0, return all.\
Example:\
\[\[1,1,1,1,1],\
\[1,0,0,1,1],\
\[1,0,0,1,1],\
\[1,1,1,1,0]], you should return \[\[\[1,1],\[2,2]],\[\[3,4],\[3,4]]]

### Solution:

**Version 1:** 左上角开始找0， 再从右下角开始找0， 最后组成result

if we assume 2d array contains one valid rectangle, the problem is very easy\
start at top left, traverse normally to the the upper left corner of rectangle when you find your first 0.\
start at bottom right, traverse in reverse will find your lower right corner when you find your first 0.

Obviously this wouldn't work if the the 2d array had a circle or non-rectangle shape

```
class Solution {
    public int[] showCorners(char[][] grid) {
        int[][] res = new int[2][];
        
        outerloop1: // used to break out of double for loop
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '0') {
                    res[0] = new int[] {i, j};
                    break outerloop1;
                }
            }
        }
        
        outerloop2:
        for (int i = grid.length-1; i >= 0; i--) {
            for (int j = grid[0].length-1; j >= 0; j--) {
                if (grid[i][j] == '0') {
                    res[1] = new int[] {i, j};
                    break outerloop2;
                }
            }
        }
        return res;
    }
}
```

**Version 2:**

从左上角开始找，找到之后再从这里开始找到长方形的右下角。

```
   public int[][] findOneRectangle(int[][] board)
    {
        int[][] result = new int[2][2];
        for(int i = 0; i< board.length; i++)
        {
            for(int j = 0; j< board[0].length; j++)
            {
                if(board[i][j] == 0)
                {
                    result[0] = {i, j};
                    int topLeftX = i;
                    int topLeftY = j;
                    
                    while(topLeftX < board.length && board[topLeftX][j] == 0)
                    {
                        topLeftX++;
                    }
                    while(topLeftY < board[0].length && board[i][topLeftY] == 0)
                    {
                        topLeftY++;
                    }
                    result[1] = {topLeftX, topLeftY};
                    break;

                }
            }
        }
        return result;
```

for multiple valid rectangles, traverse until you find a 0, that is your top left.\
now recursively find all 0's nearby, and store the greatest row-col of this rectangle, that is your bottom right.\
mark all 0's as visited.\
Again, this only works if we assume that all shapes are valid rectangles.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/wayfair/oa/karat/find-one-rectangle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.