/**
        int[][] arr = {
            { 0,   0,   1,  0},
            { 0,   0,   1,  1},
            { 1,   1,   0,  0},
            { 0,   1,   0,  0},
        };
        List list = findRectangle(arr);
        for(Coord c: list){
            c.print();
        }

        x1 = 0
        y1 = 0
        x2 = 1 
        y2 = 1 

        x1 = 3 
        y1 = 0
        x2 = 3 
        y2 = 0 

        x1 = 0 
        y1 = 3 
        x2 = 0 
        y2 = 3 

        x1 = 2 
        y1 = 2 
        x2 = 3 
        y2 = 3 
    */
    public static List findRectangle(int[][] arr){
        List list = new ArrayList<>(); 
        if(arr != null && arr.length > 0){
            int ncol = arr.length;
            int nrow = arr[0].length;
            for(int c = 0; c < ncol; c++){
                for(int r = 0; r < nrow; r++){
                    if(arr[c][r] == 0){

                        int rn = 0;
                        int rr = r;
                        while(rr < nrow && arr[c][rr] == 0){
                            rn ++;
                            rr++;
                        }

                        int cn = 0;
                        int cc = c;
                        while(cc < ncol && arr[cc][r] == 0){
                                cn++;
                                cc++;
                        }

                        Coord coord = new Coord();
                        coord.x1 = r;
                        coord.y1 = c;
                        coord.x2 = r + rn - 1;
                        coord.y2 = c + cn - 1;

                        list.add(coord);
                        
                        // flip all 0 to 1 in the current rectangle 
                        for(int y = coord.y1; y <= coord.y2; y++){
                            for(int x = coord.x1; x <= coord.x2; x++){
                                arr[y][x] = 1;
                            }
                        }
                    }
                }
            }
        }
        return list;
    }