Python - Dynamic Programming - Explained
Intuition:\nWe can convert this to 4 pieces of one dimensional array problem\nLet\'s say we have A = [1, 1, 1, 1, 0, 1, 1, 1, 1]\nWe will solve the left side 1s
**Intuition:**\nWe can convert this to 4 pieces of one dimensional array problem\nLet\'s say we have ```A = [1, 1, 1, 1, 0, 1, 1, 1, 1]```\nWe will solve the left side 1st.\nFor each index ```i (0 <= i < len(A))```, we need to find how many consecutive ones are present in the left side from the current index.\n\n```\ni = 0\nA = [1]\n```\nThere\'s no left side, hence ```dp[0] = 1```\n\n\n```\ni = 1\nA = [1, 1]\n\t\t^\n```\nThere is a "1" to the left of current index, hence ```dp[1] = dp[0] + 1 = 1+1 = 2```\n\n\n```\ni = 2\nA = [1, 1, 1]\n\t\t   ^\n```\nThere is a "1" to the left of current index, hence ```dp[2] = dp[1] + 1 = 2+1 = 3```\n\n\n```\ni = 3\nA = [1, 1, 1, 0]\n              ^\n```\t\t\t\t\nSince current index has value as 0, it cannot be extended to left (or any direction), hence dp[3] = 0\n\n\n\nAnd so on.. So the dp formula for left side is ```dp[i] = dp[i-1] + 1 if d[i] == 1```\n\nSimilary, we can formulate for right, up and down\n\nAs the problem is a matrix (2-D), we will have to add another loop to find the dp values for each row\nand dp array has to be 2-D.\n\nFor up and down, we will consider columns as rows and the column values should be in i loop and rows in j loop.\n\n```\nclass Solution:\n    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n\n        grid     = [ [1]*n for _ in range(n) ]\n        left_dp  = [ [1]*n for _ in range(n) ]\n        right_dp = [ [1]*n for _ in range(n) ]\n        down_dp  = [ [1]*n for _ in range(n) ]\n        up_dp    = [ [1]*n for _ in range(n) ]\n        \n        for i, j in mines:\n            grid[i][j] = left_dp[i][j] = right_dp[i][j] = down_dp[i][j] = up_dp[i][j] = 0\n        \n        for i in range(n):\n            \n            for j in range(1, n):\n                if left_dp[i][j] and left_dp[i][j-1] > 0:\n                    left_dp[i][j] = left_dp[i][j-1] + 1\n            \n            for j in range(n-2, -1, -1):\n                if right_dp[i][j] and right_dp[i][j+1] > 0:\n                    right_dp[i][j] = right_dp[i][j+1] + 1\n \n\n        for j in range(n):\n            \n            for i in range(1, n):\n                if up_dp[i][j] and up_dp[i-1][j] > 0:\n                    up_dp[i][j] = up_dp[i-1][j] + 1\n                    \n            for i in range(n-2, -1, -1):\n                if down_dp[i][j] and down_dp[i+1][j] > 0:\n                    down_dp[i][j] = down_dp[i+1][j] + 1\n                        \n        res = 0\n        for i in range(n):\n            for j in range(n):\n                if grid[i][j]:\n                    res = max(res, min(left_dp[i][j], right_dp[i][j], up_dp[i][j], down_dp[i][j]))\n        return res\n```
['Dynamic Programming', 'Python']