C++ - Binary Search + DP (170ms Solution)
What we do here is check whether a plus sign of order k could be found or not.\nIf it is possible  then we search in the right half of the binary search else in
What we do here is check whether a plus sign of order **k** could be found or not.\nIf it is possible  then we search in the right half of the binary search else in the left half.\n\nNow, to check if a plus sign of order k could be found or not on every valid index check whether the range sum of length **k** from that index in every four directions is **k** or not.\n\nFor finding the range sum we can use prefix sums for both column\'s and row\'s.\n\nBiggest Plus sign could be of size **ceil(n / 2)** so the search space is between **1** and **ceil(n / 2)**\n\nTime Complexity: **O(n^2 * log(n))**\nSpace Complexity: **O(n^2)**\n```\nclass Solution {\npublic:\n    vector<vector<int>> mat, row, col;\n    int n;\n    bool good(int k) {\n        for(int i = k - 1; i < n - k + 1; ++i) {\n            for(int j = k - 1; j < n - k + 1; ++j) {\n                bool flag = 1;\n\t\t\t    //in the right direction\n                flag &= row[i][j + k] - row[i][j] == k;\n\t\t\t\t//in the left direction\n                flag &= row[i][j + 1] - row[i][j - k + 1] == k;\n\t\t\t\t// in downward direction\n                flag &= col[j][i + k] - col[j][i] == k;\n\t\t\t\t// in the upward direction\n                flag &= col[j][i + 1] - col[j][i - k + 1] == k;\n                if(flag) return 1;\n            }\n        }\n        return 0;\n    }\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& a) {\n        this->n = n;\n        mat.resize(n, vector<int> (n, 1));\n        row.resize(n, vector<int> (n + 1, 0));\n        col.resize(n, vector<int> (n + 1, 0));\n        \n        for(auto x: a) mat[x[0]][x[1]] = 0;\n        \n\t\t// Calculating the prefix sum\'s for both row\'s and column\'s\n        for(int j = 0; j < n; ++j) \n            for(int i = 0; i < n; ++i) \n                row[i][j + 1] = row[i][j] + mat[i][j];\n                col[j][i + 1] = col[j][i] + mat[i][j];\n        \n        int lo = 1, hi = n - n / 2, best = 0;\n        while(lo <= hi) {\n            int mid = (lo + hi) / 2;\n            if(good(mid)) {\n\t\t\t\t//if plus sign of order mid is found\n\t\t\t\t// then set the ans to mid and search in the right half\n                best = mid;\n                lo = mid + 1;\n            } else {\n\t\t\t\t//if the plus sign could not be found search in the left half\n                hi = mid - 1;\n            }\n        }\n        \n        return best;\n    }\n};\n```
[]