C++ O(n^3) solution 226ms with explanation.
For this problem, I first think of the related problem finding largest square, and I tried DP as DP can give O(n^2) time complexity. They way I do it is use a d
For this problem, I first think of the related problem finding largest square, and I tried DP as DP can give O(n^2) time complexity. They way I do it is use a dp[N][N][4] to record each 1s consecutive 1s in 4 directions and they can be abrupt by 0. However, my code fails at last test case because of memory. Obviously, there is a tradeoff in space and time.\n\nIn order to pass I take advantage of having limited 0s on last test case and generated the following O(N^3) solution, the general idea is do bfs (I actually update everything on row and col) and update grid every time we meet a 0. There could be total N^2 0s and update board takes additional N so it's N^3.\n\nTo make things easier, I initialize the board with rules to take in count of boarder. \n\n```\nint orderOfLargestPlusSign(int N, vector<vector<int>>& mines)\n{\n    vector<vector<int>> grid(N,vector<int>(N,N));\n    \n    for(int i =0; i < N; i++)\n        for(int j =0; j< N; j++)\n        {\n            grid[i][j] = min(i-0+1,j-0+1);\n            grid[i][j] = min(grid[i][j],N-i);\n            grid[i][j] = min(grid[i][j],N-j);\n        }\n    \n    for(auto v : mines)\n    {\n        int i = v[0];\n        int j = v[1];\n        \n        for(int ii =0; ii< N;ii++)\n            grid[ii][j] = min(grid[ii][j],abs(ii-i));\n        \n        for(int jj =0; jj< N;jj++)\n            grid[i][jj] = min(grid[i][jj],abs(jj-j));\n    }\n    \n    \n    int result =0;\n    \n    for(int i =0; i < N; i++)\n        for(int j =0; j< N; j++)\n            result = max(result,grid[i][j]);\n\n    return result;\n}\n````
[]