[Python]: DP - code optimized - explanation in detail - ACCEPTED
The straightforward approach. The following code did some optimization, and it was accepted.\n\nTwo keys:\n1. convert mines from list to dictionary\n2. use try/
The straightforward approach. The following code did some optimization, and it was accepted.\n\nTwo keys:\n1. convert mines from list to dictionary\n2. use try/except instead of if/else to deal with matrix boundary issue. \n\n```\nclass Solution(object):\n    def orderOfLargestPlusSign(self, N, mines):\n        """\n        :type N: int\n        :type mines: List[List[int]]\n        :rtype: int\n        """\n        # Methods to reduce computational time:\n        # 1. convert mines from list to dictionary. O(n^3) to O(n^2)\n        # 2. use try/except instead of if else to deal with matrix boundary\n        \n        L  = [[0 for x in range(N)] for y in range(N)] #L[i][j]: number of continuous 1 from L[i][j] towards its left, L[i][j] included. \n        R  = [[0 for x in range(N)] for y in range(N)] #Right\n        U  = [[0 for x in range(N)] for y in range(N)] #Up\n        D  = [[0 for x in range(N)] for y in range(N)] #Down\n \n        dicMines = {(mine[0], mine[1]) for mine in mines} # convert mines from list to dictionary\n        \n        # calcuate L and D in O(n^2) time\n        for i in range(N):\n            for j in range(N):\n                if (i,j) not in dicMines:\n                    # use try/except instead of if/else to reduce time, if/else method is presented below as well\n                    try: L[i][j] = L[i][j-1] + 1\n                    except Exception: L[i][j] = 1\n                    try: D[i][j] = D[i-1][j] + 1\n                    except Exception: D[i][j] = 1\n                        \n                    #if/else method presented for reference\n                    #L[i][j] = L[i][j-1] + 1 if j > 0 else 1\n                    #D[i][j] = D[i-1][j] + 1 if i > 0 else 1\n                  \n        # calcuate R and U in O(n^2) time\n        for i in range (N-1, -1, -1):\n            for j in range(N-1, -1, -1):\n                if (i,j) not in dicMines:\n                    try: R[i][j] = R[i][j+1] + 1\n                    except Exception: R[i][j] = 1\n                    try: U[i][j] = U[i+1][j] + 1\n                    except Exception: U[i][j] = 1\n\n                    #R[i][j] = R[i][j+1] + 1 if j < N-1 else 1\n                    #U[i][j] = U[i+1][j] + 1 if i < N-1 else 1\n        MaxK = 0\n        MaxK = max(min(L[i][j], R[i][j], U[i][j], D[i][j]) for i in range(N) for j in range(N))\n        return (MaxK)\n```
[]