Ultra Simple Cpp Solution | Suggestions for optimization are welcomed |
Runtime: 500 ms, faster than 13.71% of C++ online submissions for Largest Plus Sign.\nMemory Usage: 89.3 MB, less than 28.63% of C++ online submissions for Larg
Runtime: 500 ms, faster than 13.71% of C++ online submissions for Largest Plus Sign.\nMemory Usage: 89.3 MB, less than 28.63% of C++ online submissions for Largest Plus Sign.\n\n```\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        \n        vector<vector<int>> grid(n,vector<int>(n,1));\n        int prefix_sum=0;\n        int sum = 0,maximum = 0;\n        \n        vector<vector<int>> left(n,vector<int>(n,0));\n        vector<vector<int>> right(n,vector<int>(n,0));\n        vector<vector<int>> top(n,vector<int>(n,0));\n        vector<vector<int>> down(n,vector<int>(n,0));\n        \n        \n        for(int i=0;i<mines.size();i++)\n            grid[mines[i][0]][mines[i][1]]=0;\n        \n        \n        //Going left\n        for(int i=0;i<n;i++){\n            prefix_sum=grid[i][0];\n            for(int j=1;j<n;j++){\n                if(!grid[i][j]){\n                    prefix_sum=0;\n                    left[i][j]=prefix_sum;\n                }\n                else{\n                    left[i][j]=prefix_sum;\n                    prefix_sum+=grid[i][j];\n                }\n            }\n        }\n            \n        // cout<<"Left Prefix"<<endl;\n        // for(int i=0;i<n;i++){\n        //     for(int j=0;j<n;j++)\n        //         cout<<left[i][j]<<" ";\n        //     cout<<endl;\n        // }\n        \n        \n        //Going right\n        for(int i=0;i<n;i++){\n            prefix_sum=grid[i][n-1];\n            for(int j=n-2;j>=0;j--){\n                if(!grid[i][j]){\n                    prefix_sum=0;\n                    right[i][j]=prefix_sum;\n                }\n                else{\n                    right[i][j]=prefix_sum;\n                    prefix_sum+=grid[i][j];\n                }\n            }\n        }\n            \n        // cout<<"Right Prefix"<<endl;\n        // for(int i=0;i<n;i++){\n        //     for(int j=0;j<n;j++)\n        //         cout<<right[i][j]<<" ";\n        //     cout<<endl;\n        // }\n        \n        \n        //Going top\n        for(int i=0;i<n;i++){\n            prefix_sum=grid[0][i];\n            for(int j=1;j<n;j++){\n                if(!grid[j][i]){\n                    prefix_sum=0;\n                    top[j][i]=prefix_sum;\n                }\n                else{\n                    top[j][i]=prefix_sum;\n                    prefix_sum+=grid[j][i];\n                }\n            }\n        }\n            \n//         cout<<"Top Prefix"<<endl;\n//         for(int i=0;i<n;i++){\n//             for(int j=0;j<n;j++)\n//                 cout<<top[i][j]<<" ";\n//             cout<<endl;\n//         }\n        \n        \n        //Going down\n        for(int i=0;i<n;i++){\n            prefix_sum=grid[n-1][i];\n            for(int j=n-2;j>=0;j--){\n                if(!grid[j][i]){\n                    prefix_sum=0;\n                    down[j][i]=prefix_sum;\n                }\n                else{\n                    down[j][i]=prefix_sum;\n                    prefix_sum+=grid[j][i];\n                }\n            }\n        }\n            \n        // cout<<"Down Prefix"<<endl;\n        // for(int i=0;i<n;i++){\n        //     for(int j=0;j<n;j++)\n        //         cout<<down[i][j]<<" ";\n        //     cout<<endl;\n        // }\n        \n        \n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i][j]){\n                sum = min(min(top[i][j],down[i][j]),min(left[i][j],right[i][j]));\n                //cout<<sum<<" ";\n                if(sum>=maximum)\n                    maximum = 1+sum;\n            }\n            //cout<<endl;\n            }\n        }\n\n        return maximum;\n    }\n};\n```
['C', 'C++']