Largest 1-Bordered Square

1139. Largest 1-Bordered Square

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int h = grid.size(), w = grid[0].size();
        vector<vector<int>> hor(h, vector<int>(w)), ver(h, vector<int>(w));
        for(int i = 0; i < h; ++i) {
            for (int j = 0;j < w; ++j) {
                ver[i][j] = hor[i][j] = grid[i][j];
                if (j && grid[i][j]) hor[i][j] += hor[i][j - 1];
                if (i && grid[i][j]) ver[i][j] += ver[i - 1][j];
            }
        }

        int result = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                int mm = hor[i][j] < ver[i][j] ? hor[i][j] : ver[i][j];
                while (result < mm) {
                    if (mm <= ver[i][j - mm + 1] && mm <= hor[i - mm + 1][j]) {
                        result = mm;
                    }
                    --mm;
                }
            }
        }
        return result * result;
    }
};

가로, 세로의 1의 길이가 얼마나 되는지 저장해 둔다.

• 가로, 세로에 대한 연속적인 1에서만 prefix sum. 가로, 세로 길이 값중 작은값(a)을 선택한다.
• 한쪽이최대 길이가 될수 있는 값이 더 작은값이므로. 가로, 세로 길이값 맵에서 (a) 인덱스만큼 뺀곳에 (a) 값 이상의 값이 있으면 답 후보로 정한다.
• (a) 길이 만큼 가봤을때 해당 위치에 값이 a 이상이라면 그만큼의 길이로 1이 있었다는 얘기가 된다.

Time: O(n^3)

• 주어진 grid 모두 순회하는데 n^2 * 값(a)만틈 루프도는데 n

Space: O(n^2)

• 가로, 세로 1의 길이를 담는 맵 각각 n^2