Leetcode: 1289. Minimum Falling Path Sum II

Mistake: Incorrect evaluation of solution's viability. First solution was \(O(n^4)\) which was solution after manual test with \(100 \times 100\) grid.
Blackbox: You solved a similar problem, where you had a fast way to pick the best result from the left and right (Leetcode: 1563. Stone Game V).
Can we break-down the problem in small and easily to solve parts? The best path that ends on \((i, j)\) is either one path that ended on its left or its right. Be \(left(j)\) the minimum path that ended on any of \((i-1, 0), (i-1, 1), .., (i-1, j)\) cells, and \(right(j)\) the minimum path that ended on any of \((i-1, j+1), (i-1, j+2), .., (i-1, M-1)\). Given that, we can compute \(dp[i][j]=grid[i][j]+min(left[j-1], right[j+1])\). Time and space complexity is \(O(n^2)\).

from typing import List


class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)
        M = len(grid[0])

        if N == 1 and M == 1:
            return grid[0][0]

        dp = [[float("inf")] * M for _ in range(N)]
        left = [float("inf")] * M
        right = [float("inf")] * M

        for i in range(N):
            for j in range(M):
                if i == 0:
                    dp[i][j] = grid[i][j]
                    continue

                dp[i][j] = grid[i][j]
                if j == 0:
                    dp[i][j] += right[j + 1]
                elif j == M - 1:
                    dp[i][j] += left[j - 1]
                else:
                    dp[i][j] += min(left[j - 1], right[j + 1])

            if i < M - 1:
                for j in range(M):
                    left[j] = min(dp[i][j], float("inf") if j == 0 else left[j - 1])
                for j in range(M - 1, -1, -1):
                    right[j] = min(
                        dp[i][j], float("inf") if j == M - 1 else right[j + 1]
                    )

        return min(dp[N - 1][j] for j in range(M))


assert Solution().minFallingPathSum([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == 13
assert Solution().minFallingPathSum([[7]]) == 7