Description #
Given a square array of integers A, we want the minimum sum of a falling path through A.
A falling path starts at any element in the first row, and chooses one element from each row. The next row’s choice must be in a column that is different from the previous row’s column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]] Output: 12Explanation: The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]The falling path with the smallest sum is
[1,4,7], so the answer is 12.
(From the problem description)
Test Vectors #
| square | shortest | solution |
|---|---|---|
| [[1,2,3],[4,5,6],[7,8,9]] | 12 | [1,4,7] |
Problem Analysis #
Another problem suitable for dynamic programming. As usual I’ll work incrementally:
- Start with a top-down recursive backtracking solution with (potentially) exponential runtime.
- Enhance the backtracking with memorizing (dynamic programming)
- Convert the top-down memorizing backtracking solution into a bottom-up incremental version.
Solutions #
Tests #
This leads to the following tests:
import os
import pytest
class BaseTestClass:
def test_example_1(self):
assert 12 == self.minFallingPathSum([[1,2,3],[4,5,6],[7,8,9]])
def test_negative_numbers(self):
assert -20 == self.minFallingPathSum([[1,-5,1,1], [1,-5,1,1],[1,-5,1,1],[1,-5,1,1]] )
def test_1x1(self):
# edge case
assert 9 == self.minFallingPathSum([[9]])
Solution 1: Backtracking #
A straight forward recursive solution from the problem description.
from typing import List
class Solution:
def _minFallingPathSum(self, A: List[List[int]], col:int, row:int) -> int:
if col == len(A):
return 0
first_row = max(0, row - 1)
last_row = min(len(A) - 1, row + 1)
best_paths = [ A[col][row] + self._minFallingPathSum(A, col + 1, row) for row in range(first_row, last_row + 1)]
return min(best_paths)
def minFallingPathSum(self, A: List[List[int]]) -> int:
# start with the leftmost column and iterate
# get the best value
# The first column is special because we can use each row
best_paths = [ A[0][row] + self._minFallingPathSum(A, 1, row) for row in range(0, len(A))]
return min(best_paths)
Test Results #
With the following test result:
============================= test session starts ==============================
platform linux -- Python 3.7.5, pytest-3.10.1, py-1.8.0, pluggy-0.12.0
benchmark: 3.2.2 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/jens/Documents/leetcode.com/931-minimum-falling-path-sum, inifile:
plugins: benchmark-3.2.2, profiling-1.7.0
collected 3 items
test_1a-solution.py ... [100%]
============================ slowest test durations ============================
(0.00 durations hidden. Use -vv to show these durations.)
=========================== 3 passed in 0.03 seconds ===========================
Tests ran in 0.17997179499070626 seconds
Analysis #
The test results clearly show that this solution will not work for larger squares, due to the large runtime.
The problem size is defined by the size of the square, namely the number of rows/columns. Let \(n=len(A)\), e.g 3 for a 3x3 matrix.
- The first column (\(A[0]\)) takes \(n\) steps, one for each row
- For each of the steps from column 0, 2 or 3 steps are needed in column 1
- For each of the steps from column 1, 2 or 3 steps are needed in column 2
- … repeat n times
For each new column, the total work is (at least) doubled (or tripled). This makes the runtime \(O(n*2^{n-1})\).
Solution 2: Backtracking with memorizing #
from typing import List
class Solution:
def _minFallingPathSum(self, col:int, row:int) -> int:
if col == len(self.A):
return 0
if self.optimal[col][row] is None:
first_row = max(0, row - 1)
last_row = min(len(self.A) - 1, row + 1)
best_paths = [self.A[col][row] + self._minFallingPathSum(col + 1, row) for row in range(first_row, last_row + 1)]
self.optimal[col][row] = min(best_paths)
return self.optimal[col][row]
def minFallingPathSum(self, A: List[List[int]]) -> int:
self.A = A
self.optimal = [ [None] * len(A) for x in range(0, len(A)) ]
# start with the leftmost column and iterate
# get the best value
# The first column is special because we can use each row
best_paths = [ self.A[0][row] + self._minFallingPathSum(1, row) for row in range(0, len(self.A))]
return min(best_paths)
Test Results #
With the following test result:
============================= test session starts ==============================
platform linux -- Python 3.7.5, pytest-3.10.1, py-1.8.0, pluggy-0.12.0
benchmark: 3.2.2 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/jens/Documents/leetcode.com/931-minimum-falling-path-sum, inifile:
plugins: benchmark-3.2.2, profiling-1.7.0
collected 3 items
test_1b-solution.py ... [100%]
============================ slowest test durations ============================
(0.00 durations hidden. Use -vv to show these durations.)
=========================== 3 passed in 0.02 seconds ===========================
Tests ran in 0.16927009900973644 seconds
Analysis #
This solution is optimal in terms of omitting unneeded calculations. Thus it runs in \(O(n^2)\).
Closely looking at the shows room for improvement: The optimal values for column \(a\) are only used to calculate the optimal values for column \(a-1\).
Solution 3: Iterative #
from typing import List
class Solution:
def minFallingPathSum(self, A: List[List[int]]) -> int:
# we look at column col_idx and update column col_idx - 1
for col_idx in range(len(A) - 1, 0, -1):
# print(f" Analysing column {col_idx}: {A[col_idx]}\n")
for row_idx in range(0, len(A)):
first_row = max(0, row_idx - 1)
last_row = min(len(A) - 1, row_idx + 1)
# print(f" ... A[{col_idx - 1}][{row_idx}] = A[{col_idx - 1}][{row_idx}] + min({A[col_idx][first_row:last_row + 1]}) \n")
A[col_idx - 1][row_idx] = A[col_idx - 1][row_idx] + min(A[col_idx][first_row:last_row + 1])
# print(f" ... {A}\n")
return min(A[0])
Test Results #
With the following test result:
============================= test session starts ==============================
platform linux -- Python 3.7.5, pytest-3.10.1, py-1.8.0, pluggy-0.12.0
benchmark: 3.2.2 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/jens/Documents/leetcode.com/931-minimum-falling-path-sum, inifile:
plugins: benchmark-3.2.2, profiling-1.7.0
collected 3 items
test_1c-solution.py ... [100%]
============================ slowest test durations ============================
(0.00 durations hidden. Use -vv to show these durations.)
=========================== 3 passed in 0.02 seconds ===========================
Tests ran in 0.1694287589925807 seconds
Analysis #
This solution is optimal in terms of omitting unneeded calculations. Thus it runs in \(O(n^2)\). The costly recursion also has been replaced by an iterative loop. The statistics at leetcode are not satisfactory (132ms, faster than 38%). More than 80% of the solutions are between 110ms and 140ms and have a very similar structure. So I guess A lot of the difference can be attributed to fluctuations in the servers performance.
In any case the goal was to work through the three steps of optimizations with dynamic programming:
- Recursive, top down backtracking solution with mostly exponential runtime.
- Recursive, top down backtracking solution while caching intermediate results. Most of the times this already has an optimal runtime complexity and adds some space complexity.
- Convert the recursive top down version into an iterative bottom up solution with unchanged runtime complexity and often greatly reduced space complexity. The main performance boost there stems from the elimination of recursion.
Summary #
| Solution | Correct | Status | Runtime | Memory | Language |
|---|---|---|---|---|---|
| Solution #3 | Yes | Submission | 132 ms, faster than 38.27% | 13.6 MB, less than 83.33% | Python3 |