C++ || Prefix Sum Concept || Dynamic programming || With Explanations
\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        // very good ques\n      // dp approach\n      // TIME
```\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        // very good ques\n      // dp approach\n      // TIME COMPLEXITY= O(N^2)\n      //Space COMPLEXITY = O(N^2)\n        vector<vector<int>>matrix(n,vector<int>(n,1));  // forming the matrix\n        vector<vector<int>>left(n,vector<int>(n,1));   //  will do prefix sum up to left[i][j]\n      vector<vector<int>>up(n,vector<int>(n,1));   // will do prefix sum up to up[i][j]\n      vector<vector<int>>right(n,vector<int>(n,1));  // will do prefix sum up to right[i][j]\n      vector<vector<int>>down(n,vector<int>(n,1));  // will do prefix sum up to down[i][j]\n        for(auto x:mines) {matrix[x[0]][x[1]]=0; left[x[0]][x[1]]=0 ; up[x[0]][x[1]]=0; right[x[0]][x[1]]=0; down[x[0]][x[1]]=0;}\n        for(int i=0;i<n;i++){\n           for(int j=1;j<n;j++){\n              left[i][j]=matrix[i][j]?1+left[i][j-1]:0;\n           }\n        }\n       for(int i=1;i<n;i++){\n           for(int j=0;j<n;j++){\n              up[i][j]=matrix[i][j]?1+up[i-1][j]:0;\n           }\n        }\n       for(int i=0;i<n;i++){\n           for(int j=n-2;j>=0;j--){\n              right[i][j]=matrix[i][j]?1+right[i][j+1]:0;\n           }\n        }\n      for(int i=n-2;i>=0;i--){\n           for(int j=0;j<n;j++){\n              down[i][j]=matrix[i][j]?1+down[i+1][j]:0;\n           }\n        }\n      int ans=0;\n      for(int i=0;i<n;i++){\n           for(int j=0;j<n;j++){\n              if(matrix[i][j]){\n                ans=max(ans,min(min(left[i][j],right[i][j]),min(up[i][j],down[i][j])));\n              }\n           }\n        }\n      return ans;\n    }\n};\n```
['C']