C ++ || DP SOLUTION || Intuition Explained ||
Intution and Thought Process :\n\n Idea is to store the length of longest consecutive 1\'s in all four directions. \n For this we need to have 4 seperate matrix
**Intution and Thought Process :**\n\n* Idea is to store the length of longest consecutive 1\'s in all four directions. \n* For this we need to have 4 seperate matrix that stores the length for **left, right, up, down.**\n* And then for every 1\'s in the grid, we need to find the minimum of left, right, up, and down. That will be the order of plus. \n# Code : \n```\nint orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n     \n\tvector<vector<int>> grid(n, vector<int>(n, 1));\n\tint orderOfPlus = 0;\n\tfor(auto& mine : mines)\n\t{\n\t\tgrid[mine[0]][mine[1]] = 0;\n\t}\n\n\t// UP and LEFT\n\tvector<vector<int>> up(n, vector<int>(n, 0));\n\tvector<vector<int>> left(n, vector<int>(n, 0));\n\tfor(int i=0; i<n; i++)\n\t{\n\t\tfor(int j=0; j<n; j++)\n\t\t{\n\t\t\tif(grid[i][j])\n\t\t\t{\n\t\t\t\tup[i][j] = 1;\n\t\t\t\tleft[i][j] = 1;\n\t\t\t\tif(i > 0) up[i][j] = 1 + up[i-1][j];\n\t\t\t\tif(j > 0) left[i][j] = 1 + left[i][j-1];\n\t\t\t}\n\t\t}\n\t}\n\n\t// DOWN and RIGHT\n\tvector<vector<int>> down(n, vector<int>(n, 0));\n\tvector<vector<int>> right(n, vector<int>(n, 0));\n\tfor(int i=n-1; i>=0; i--)\n\t{\n\t\tfor(int j=n-1; j>=0; j--)\n\t\t{\n\t\t\tif(grid[i][j])\n\t\t\t{\n\t\t\t\tdown[i][j] = 1;\n\t\t\t\tright[i][j] = 1;\n\t\t\t\tif(i<n-1) down[i][j] = 1 + down[i+1][j];\n\t\t\t\tif(j<n-1) right[i][j] = 1 + right[i][j+1];\n\t\t\t}\n\t\t}\n\t}\n\n\t// Find min in all 4 directions\n\tfor(int i=0; i<n; i++)\n\t{\n\t\tfor(int j=0; j<n; j++)\n\t\t{\n\t\t\tif(grid[i][j])\n\t\t\t{\n\t\t\t\tint order = min({up[i][j], left[i][j], down[i][j], right[i][j]});\n\t\t\t\torderOfPlus = max(orderOfPlus, order);\n\t\t\t}\n\t\t}\n\t}\n\treturn (orderOfPlus);\n}\n```\n**Time : O(N^2)**\n**Space :  O(N^2) **\n\n**Follow UP :**\n* Here, we can do some more optimizations. Like, instead of taking 4 different matrix for each direction, we can take a single DP matrix. \n* Also, instead of computing separately for *UP, LEFT* and *DOWN, RIGHT*, we can put them into one nested loop.\n\n*If you liked the solution do give it an upvote :)*
['Dynamic Programming']