# 764. Largest Plus Sign

• Time: $O(N^2)$
• Space: $O(N^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public: int orderOfLargestPlusSign(int n, vector>& mines) { vector> grid(n, vector(n, n)); for (const vector& mine : mines) grid[mine[0]][mine[1]] = 0; // Extend four directions, if meet 0, need to start over from 0 for (int i = 0; i < n; ++i) { for (int j = 0, leftToRight = 0; j < n; ++j) { leftToRight = (grid[i][j] == 0 ? 0 : leftToRight + 1); grid[i][j] = min(grid[i][j], leftToRight); } for (int j = n - 1, rightToLeft = 0; j >= 0; --j) { rightToLeft = (grid[i][j] == 0 ? 0 : rightToLeft + 1); grid[i][j] = min(grid[i][j], rightToLeft); } for (int j = 0, upToDown = 0; j < n; ++j) { upToDown = (grid[j][i] == 0 ? 0 : upToDown + 1); grid[j][i] = min(grid[j][i], upToDown); } for (int j = n - 1, downToUp = 0; j >= 0; --j) { downToUp = (grid[j][i] == 0) ? 0 : downToUp + 1; grid[j][i] = min(grid[j][i], downToUp); } } int ans = 0; for (const vector& row : grid) ans = max(ans, *max_element(begin(row), end(row))); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public int orderOfLargestPlusSign(int n, int[][] mines) { int[][] grid = new int[n][n]; Arrays.stream(grid).forEach(row -> Arrays.fill(row, n)); for (int[] mine : mines) grid[mine[0]][mine[1]] = 0; // Extend four directions, if meet 0, need to start over from 0 for (int i = 0; i < n; ++i) { for (int j = 0, leftToRight = 0; j < n; ++j) { leftToRight = (grid[i][j] == 0 ? 0 : leftToRight + 1); grid[i][j] = Math.min(grid[i][j], leftToRight); } for (int j = n - 1, rightToLeft = 0; j >= 0; --j) { rightToLeft = (grid[i][j] == 0 ? 0 : rightToLeft + 1); grid[i][j] = Math.min(grid[i][j], rightToLeft); } for (int j = 0, upToDown = 0; j < n; ++j) { upToDown = (grid[j][i] == 0 ? 0 : upToDown + 1); grid[j][i] = Math.min(grid[j][i], upToDown); } for (int j = n - 1, downToUp = 0; j >= 0; --j) { downToUp = (grid[j][i] == 0) ? 0 : downToUp + 1; grid[j][i] = Math.min(grid[j][i], downToUp); } } int ans = 0; for (int[] row : grid) ans = Math.max(ans, Arrays.stream(row).max().getAsInt()); return ans; } }