Python Solution using DP for Trapping Rain Water II: Is one test case dubious?
This solution passes 17/40 test cases, however, one of the test cases seems to be dubious to me. \n\nTest Case Input : [[12,13,1,12],[13,4,13,12],[13,8,10,12],[
This solution passes 17/40 test cases, however, one of the test cases seems to be dubious to me. \n\nTest Case Input : [[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]]\nMy output: 15\nExpected output: 14\n\nMy solution :\n\n\'\'\'\nclass Solution(object):\n    def trapRainWater(self, heightMap):\n        """\n        :type heightMap: List[List[int]]\n        :rtype: int\n        """\n        if not heightMap:\n            return 0\n        m=len(heightMap[0])\n        n=len(heightMap)\n        \n        ans = 0\n        \n        left = [[0 for i in range(m)] for j in range(n)]\n        right = [[0 for i in range(m)] for j in range(n)]\n        up = [[0 for i in range(m)] for j in range(n)]\n        down = [[0 for i in range(m)] for j in range(n)]\n        for i in range(n):\n            left[i][0]=heightMap[i][0]\n            right[i][m-1]=heightMap[i][m-1]\n        for i in range(m):\n            up[0][i]=heightMap[0][i]\n            down[n-1][i]=heightMap[n-1][i]\n        \n        for i in range(n):\n            for j in range(1, m):\n                left[i][j]=max(heightMap[i][j], left[i][j-1])\n        \n        for i in range(n):\n            for j in range(m-2, -1, -1):\n                right[i][j]=max(heightMap[i][j], right[i][j+1])\n            \n        for i in range(m):\n            for j in range(1, n):\n                up[j][i]=max(heightMap[j][i], up[j-1][i])\n        \n        for i in range(m):\n            for j in range(n-2, -1, -1):\n                down[j][i]=max(heightMap[j][i], down[j+1][i])\n        \n        for i in range(1, n-1):\n            for j in range(1, m-1):\n                ans+=abs(min(left[i][j], right[i][j], up[i][j], down[i][j])-heightMap[i][j])\n            print(ans)\n                \n        return ans\n\'\'\'
['Dynamic Programming', 'Python']