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.