C++ | Easy To Understand | Prefix - Sum Approach
\nThis is not the fastest solution but it is very easy to understand and come up during an actual interview. Pls feel free to optimise this solution!\n# Code\n\
\nThis is not the fastest solution but it is very easy to understand and come up during an actual interview. Pls feel free to optimise this solution!\n# Code\n```\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        vector<vector<int>> up(n, vector<int>(n, 0)), down(n, vector<int>(n, 0)), left(n, vector<int>(n, 0)), right(n, vector<int>(n, 0));\n\n        unordered_map<int, unordered_map<int,int>> mp;\n        for(auto &p : mines)\n            mp[p[0]][p[1]]++;\n\n//below code that includes 4 double loops are used for storing prefix sum of 1\'s in left, right,up and down direction.\n        for(int j = 0; j < n; j++){\n            for(int i = 0; i < n; i++){\n                if(mp[i].find(j) != mp[i].end())\n                    up[i][j] = 0;\n                else if(i == 0)\n                    up[i][j] = 1;\n                else\n                    up[i][j] = 1 + up[i - 1][j];\n            }\n        }\n\n        for(int j = 0; j < n; j++){\n            for(int i = n - 1; i >= 0; i--){\n                if(mp[i].find(j) != mp[i].end())\n                    down[i][j] = 0;\n                else if(i == n - 1)\n                    down[i][j] = 1;\n                else\n                    down[i][j] = 1 + down[i + 1][j];\n            }\n        }\n\n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < n; j++){\n                if(mp[i].find(j) != mp[i].end())\n                    left[i][j] = 0;\n                else if(j == 0)\n                    left[i][j] = 1;\n                else\n                    left[i][j] = 1 + left[i][j - 1];\n            }\n        }\n\n        for(int i = 0; i < n; i++){\n            for(int j = n - 1; j >= 0; j--){\n                if(mp[i].find(j) != mp[i].end())\n                    right[i][j] = 0;\n                else if(j == n - 1)\n                    right[i][j] = 1;\n                else\n                    right[i][j] = 1 + right[i][j + 1];\n            }\n        }\n\n\n        int res = 0;\n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < n; j++){\n                // cout<<left[i][j]<<" "<<right[i][j]<<" "<<up[i][j]<<" "<<down[i][j]<<endl;\n                res = max(res, min(left[i][j], min(right[i][j], min(up[i][j], down[i][j]))));\n                //the \'order\' of plus sign will be the minimum of prefix sums from the four sides.\n            }\n        }\n        return res;\n    }\n};\n```
['Dynamic Programming', 'Prefix Sum', 'C++']