DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

1

Minimum Falling Path Sum

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

SOLUTION:

class Solution:
    def minSum(self, matrix, i, j, m, n):
        if i == m - 1:
            return matrix[i][j]
        if (i, j) in self.cache:
            return self.cache[(i, j)]
        minPath = float('inf')
        for col in [j - 1, j, j + 1]:
            if 0 <= col < n:
                minPath = min(minPath, matrix[i][j] + self.minSum(matrix, i + 1, col, m, n))
        self.cache[(i, j)] = minPath
        return minPath

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        self.cache = {}
        minPath = float('inf')
        for i in range(n):
            minPath = min(minPath, self.minSum(matrix, 0, i, m, n))
        return minPath
Enter fullscreen mode Exit fullscreen mode

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️