< Back




931. Minimum Falling Path Sum

This is a graph represented as a matrix, with the cost to reach a node along the path represented by
a postive number in the node's representative cell in the matrix. Traversing this graph, we can make
as little as two choices, or at most three choices - to go down, down and left, or down and right.

These choices are restricted by our location within the matrix. If we're at the rightmost column, we
can only choose down and left or down. Alternatively, if we're at the leftmost column, we can only
choose down and right or down. Otherwise, we can choose all three.

We also notice that the input will always be size `n * n` - so we don't have to worry about
situations where only one choice (down) will be available.

Finally, we know that in the last row `matrix[n - 1][:]`, no more choices can be made for any cell -
these are all final nodes within a path in the graph.

We pursue a bottom-up dynamic programming approach and, because we using a bottom-up approach, we
can reuse the input matrix to store our choices and memoization table, saving us some space.

We know that no choices can be made in the last row, `matrix[n - 1][:]`, so we start making choices
from the penultimate row, `matrix[n - 2][:]`. Start from the rightmost column and moving left, we
make sure that in the rightmost and leftmost column, we only decide between two choices:

* Down and left or down
* Down and right or down

Otherwise, we decide between three choices:

* Down and left, down and right, or down

At each cell, we find the minimum cost across our three choices and add it to the current cost of
the current cell, essentially choose the minimum cost path from the current node to the falling node
in the graph. These choices build upon each other as we backtrack upwards to the preceding row.
Eventually, the top row, `matrix[0][:]`, will have the values of the minimum falling path from each
starting node - we return the minimum of these minimums, `min(matrix[0])`.

The solution is as follows:


  class Solution:
      def minFallingPathSum(self, matrix: List[List[int]]) -> int:
          n = len(matrix)

          for i in range(n - 2, -1, -1):
              for j in range(n - 1, -1, -1):
                  matrix[i][j] += min(
                      matrix[i + 1][j],
                      matrix[i + 1][max(0, j - 1)],
                      matrix[i + 1][min(n - 1, j + 1)],
                  )

          return min(matrix[0])


_ Time Complexity:

  O(n^2) - Where n is the size of the rows and columns in the matrix, we iterate through all cells
  provided.

_ Space Complexity:

  O(1) - We reuse the existing space provided in the input.