Leetcode minimum path sum

Question

Link here

I'll include a solution in Python and C++ and you can review one. I'm mostly interested in reviewing the C++ code which is a thing I recently started learning; those who don't know C++ can review the Python code. Both solutions share similar logic, so the review will apply to any.

---

Problem statement

Given a \$ m \times n \$ grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

Output: 7

Explanation: Because the path \$ 1 \to 3 \to 1 \to 1 \to 1 \$ minimizes the sum.

In the python implementation, there is PathFinder class that has some extra methods for visualizing the resulting minimum or maximum path (for fun purposes), the problem requirements are covered only by the first 2 methods _get_possible_moves() and get_path_sum().

path_sum.py

import pandas as pd
class PathFinder:
 """
 Path maximizer / minimizer
 """
 def __init__(self, matrix, start_point=(0, 0)):
 """
 Initialize finder settings.
 Args:
 matrix: 2D list
 start_point: x, y coordinates to start from.
 """
 x1, y1 = start_point
 self.matrix = matrix[x1:][y1:]
 self.seen = {}
 self.x_size = len(self.matrix)
 self.y_size = len(self.matrix[0])
 self.end_x = self.x_size - 1
 self.end_y = self.y_size - 1
 self.initial_frame, self.processed_frame = (None, None)
 def _get_possible_moves(self, x, y):
 """
 Get possible next moves.
 Args:
 x: x coordinate.
 y: y coordinate.
 Returns:
 possible_moves.
 """
 possible_moves = []
 if x < self.end_x:
 possible_moves.append([x + 1, y])
 if y < self.end_y:
 possible_moves.append([x, y + 1])
 return possible_moves
 def get_path_sum(self, x, y, mode='min'):
 """
 Get minimum / maximum path sum following right and down steps only.
 Args:
 x: x coordinate.
 y: y coordinate.
 mode: 'min' or 'max'
 Returns:
 Minimum or Maximum path sum.
 """
 assert mode in ('min', 'max'), f'Invalid mode {mode}'
 if (x, y) in self.seen:
 return self.seen[x, y]
 current = self.matrix[x][y]
 if x == self.end_x and y == self.end_y:
 return current
 possible_moves = self._get_possible_moves(x, y)
 results = [
 current + self.get_path_sum(*possible, mode) for possible in possible_moves
 ]
 current_best = min(results) if mode == 'min' else max(results)
 self.seen[x, y] = current_best
 return current_best
 def _create_frames(self):
 """
 Create pandas DataFrame to preview path followed.
 Returns:
 Initial frame and a copy.
 """
 pd.set_option('expand_frame_repr', False)
 initial_frame = pd.DataFrame(self.matrix)
 return initial_frame, initial_frame.copy()
 def _modify_coordinate(self, x, y):
 """
 Mark a coordinate that is in the min/max path.
 Args:
 x: x coordinate.
 y: y coordinate.
 Returns:
 None
 """
 n = self.processed_frame.loc[x, y]
 self.processed_frame.loc[x, y] = f'({n})'
 def _update_xy(self, x, y):
 """
 Follow and mark 1 step of the path.
 Args:
 x: x coordinate.
 y: y coordinate.
 Returns:
 x, y update.
 """
 current_n = self.matrix[x][y]
 current_best = self.seen[x, y]
 right_best = self.seen[x, y + 1]
 down_best = self.seen[x + 1, y]
 if current_best - right_best == current_n:
 self._modify_coordinate(x, y + 1)
 return x, y + 1
 if current_best - down_best == current_n:
 self._modify_coordinate(x + 1, y)
 return x + 1, y
 def draw_path(self):
 """
 Draw path followed using seen values.
 Returns:
 2 pandas DataFrames one containing path and another empty.
 """
 self.initial_frame, self.processed_frame = self._create_frames()
 x, y = 0, 0
 self._modify_coordinate(x, y)
 while x <= self.end_x or y <= self.end_y:
 if y == self.end_y:
 for i in range(x + 1, self.x_size):
 self._modify_coordinate(i, y)
 break
 if x == self.end_x:
 for i in range(y + 1, self.y_size):
 self._modify_coordinate(x, i)
 break
 x, y = self._update_xy(x, y)
 return self.initial_frame, self.processed_frame
if __name__ == '__main__':
 m = [
 [7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5],
 [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6],
 [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8],
 [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4],
 [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4],
 [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9],
 [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4],
 [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2],
 [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3],
 [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7],
 [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7],
 [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9],
 ]
 finder = PathFinder(m)
 print(finder.get_path_sum(0, 0))
 print(finder.draw_path()[1])

Out:

Minimum: 85
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 (7) (1) (3) (5) 8 9 9 2 1 9 0 8 3 1 6 6 9 5
1 9 5 9 (4) (0) 4 8 8 9 5 7 3 6 6 6 9 1 6
2 8 2 9 1 (3) (1) 9 7 2 5 3 1 2 4 8 2 8 8
3 6 7 9 8 4 (8) (3) (0) 4 0 9 6 6 0 0 5 1 4
4 7 1 3 1 8 8 3 (1) (2) (1) (5) (0) (2) 1 9 1 1 4
5 9 5 4 3 5 6 1 3 6 4 9 7 (0) 8 0 3 9 9
6 1 4 2 5 8 7 7 0 0 7 1 2 (1) 2 7 7 7 4
7 3 9 7 9 5 8 9 5 6 9 8 8 (0) (1) (4) (2) 8 2
8 1 5 2 2 2 5 6 3 9 3 1 7 9 6 8 (6) 8 3
9 5 7 8 3 8 8 3 9 9 8 1 9 2 5 4 (7) 7 7
10 2 3 2 4 8 5 1 7 2 9 5 2 4 2 9 (2) 8 7
11 0 1 6 1 1 0 0 6 5 4 3 4 3 7 9 (6) (1) (9)

In the c++ implementation, I used the same algorithm, there is std::vector<std::vector<int>> seen that has the previously calculated sum per location and as this vector does not grow in size, I thought maybe replacing it with a std::array<std::array<int, m >, n> where m, n are the matrix dimensions but I get non-type template argument is not a constant expression and I learned that this might not be possible. The proper way is replacing m, n with actual numbers, otherwise it won't work, so I went with the vector.

path_sum.h

#ifndef LEETCODE_PATH_SUM_H
#define LEETCODE_PATH_SUM_H
#include <vector>
#include <string>
int path_sum(const std::vector<std::vector<int>> &matrix, int x, int y,
 std::vector<std::vector<int>> &seen, int empty_value = -1,
 const std::string& mode = "min");
#endif //LEETCODE_PATH_SUM_H

path_sum.cpp

#include "path_sum.h"
#include <algorithm>
#include <iostream>
int path_sum(const std::vector<std::vector<int>> &matrix, int x, int y,
 std::vector<std::vector<int>> &seen, int empty_value,
 const std::string &mode) {
 int seen_value{seen[x][y]};
 if (seen_value != empty_value)
 return seen_value;
 auto x_end = matrix.size() - 1;
 auto y_end = matrix[0].size() - 1;
 int current = matrix[x][y];
 if (x == x_end && y == y_end)
 return current;
 std::vector<int> results;
 if (x < x_end)
 results.push_back(
 current + path_sum(matrix, x + 1, y, seen, empty_value, mode));
 if (y < y_end)
 results.push_back(
 current + path_sum(matrix, x, y + 1, seen, empty_value, mode));
 int current_best;
 switch (results.size()) {
 case 1:
 seen[x][y] = results[0];
 return results[0];
 case 2:
 int n1{results[0]};
 int n2{results[1]};
 current_best = (mode == "min") ? std::min(n1, n2) : std::max(n1, n2);
 }
 seen[x][y] = current_best;
 return current_best;
}
int main() {
 std::vector<std::vector<int>> matrix{
 {7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5},
 {9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6},
 {8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8},
 {6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4},
 {7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4},
 {9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9},
 {1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4},
 {3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2},
 {1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3},
 {5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7},
 {2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7},
 {0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9}
 };
 std::vector<std::vector<int>> seen(matrix.size(),
 std::vector<int>(matrix[0].size(), -1));
 std::cout << "Minimum: " << path_sum(matrix, 0, 0, seen);
}

• Loki Astari: One word: Dijkstra.
• watch-this: I thought about using it but felt like an overkill for such a simple exercise.
• Loki Astari: Then you wrote this and though it would have been simpler to write Dijkstra?
• watch-this: It felt more intuitive, but i agree Dijkstra is well suited for these things
• superb rain: Doesn't get accepted, produces ModuleNotFoundError: No module named 'pandas'. It's also lacking the Solution class.

Answer 1

Python

• Naming: self.x_size and self.y_size can be shorten to self.m and self.n, following from the problem description.
• Initialization:

  x1, y1 = start_point
  self.matrix = matrix[x1:][y1:]
  

  I think that can be safely changed to:

  self.matrix = matrix
  

• Documentation:

  def _get_possible_moves(self, x, y):
   """
   Get possible next moves.
   Args:
   x: x coordinate.
   y: y coordinate.
   Returns:
   possible_moves.
   """
  

  Personally, I don't find it useful. Would be better to explain what are the possible moves.

Performance

Runtime: 208 ms, faster than 5.31% of Python3 online submissions for Minimum Path Sum.
Memory Usage: 20.6 MB, less than 5.07% of Python3 online submissions for Minimum Path Sum.

The recursive approach is nice but typically slower than the iterative one. In this case, building an iterative solution using dynamic programming seems to be faster. This is an example:

def get_path_sum(matrix):
 m, n = len(matrix), len(matrix[0])
 
 for row in range(1,m):
 matrix[row][0] = matrix[row-1][0] + matrix[row][0]
 
 for col in range(1,n):
 matrix[0][col] = matrix[0][col] + matrix[0][col-1]
 
 for row in range(1,m):
 for col in range(1,n):
 matrix[row][col] = min(matrix[row][col-1],matrix[row-1][col]) + matrix[row][col]
 return matrix[-1][-1]

Runtime from LeetCode:

Runtime: 92 ms
Memory Usage: 15.6 MB

Memoization in advance

As I mentioned in the comments, the dynamic programming solution has some advantages (in terms of performances) compared to your recursive solution:

1. There is no recursion overhead
2. It doesn't use additional data structures like seen
3. It has \$n*m\$ iterations, while your solution does \2ドル*n*m\$ recursive calls.

The last point can be improved by doing the memoization in advance:

def get_path_sum(self, x, y, mode='min'):
 # ...
 # Here remove the memoization: if (x, y) in self.seen
 # ...
 results = []
 for move in self._get_possible_moves(x, y):
 # Call recursive function only if needed
 if move in self.seen:
 results.append(current + self.seen[move])
 else:
 results.append(current + self.get_path_sum(*move, mode))
 # ...

Now, the number of recursive calls is \$n*m\$ (ignoring the borders of the matrix). Note that _get_possible_moves returns a list of tuples or even better a generator (like @superbrain answer).

• watch-this: Why the recursive approach is slow? and self.matrix = matrix[x1:][y1:] is meant for cases where start coordinates are not (0, 0) being the default value, it's not required though, thanks
• Marc: @bullseye what I am saying is that taken an iterative and a recursive implementation of the same function, the iterative is typically faster. However, the example I provided is not really your function translated to iterative, so maybe not the best evidence.
• Marc: @bullseye the iterative solution has no "recursive overhead" and doesn't use additional data structures like seen and possible_moves, maybe that's why. Also your solution has two recursive calls for each element, mitigated with memoization but still.
• Deduplicator: Especially in Python. Remember that Python has no proper tail calls. Actually, tail-call-optimization is forbidden.
• superb rain: @bullseye matrix[x1:][y1:] doesn't even work.

Answer 2

This looks simpler:

#include <vector>
#include <iostream>
using Row = std::vector<int>;
using Matrix = std::vector<Row>;
int getMinCostToParent(Matrix const& matrix, int y, int x)
{
 // The min cost to the parent is the min cost
 // to either the parent above you or to your left.
 // If you are on the edge of the use the other value.
 return (x == 0 && y == 0) ? 0
 : (x == 0) ? matrix[y-1][x]
 : (y == 0) ? matrix[y][x-1]
 : std::min(matrix[y-1][x], matrix[y][x-1]);
}
int path_sum(Matrix matrix)
{
 // Pass `matrix` by value to get a copy.
 // As we are going to overwrite its content.
 // For each square calculate the min cost to get there.
 for (int y = 0; y < matrix.size(); ++y) {
 for (int x = 0; x < matrix[y].size(); ++x) {
 matrix[y][x] = getMinCostToParent(matrix, y, x) + matrix[y][x];
 }
 }
 // The bottom right square contains the total cost.
 return matrix.back().back();
}
int main() {
 Matrix matrix{
 {7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5},
 {9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6},
 {8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8},
 {6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4},
 {7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4},
 {9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9},
 {1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4},
 {3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2},
 {1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3},
 {5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7},
 {2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7},
 {0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9}
 };
 std::cout << "Minimum: " << path_sum(matrix) << "\n";
}

Answer 3

Well, as Marc said, your current recursive algorithm is wasteful.

The way he uses dynamic programming has an advantage, namely you can easily trace the path taken, but also a decided disadvantage, you are destroying the input-matrix.

If you don't care about extracting the way taken, you only need two rows (or columns, symmetry is nice) for calculations.

Now, your inexperience with C++ (and more experience with Python) shows, so let's dissect that solution:

1. Creating a header-file for the main file is uncommon. Especially in your case, where you don't need forward-declarations at all.

2. You shouldn't pass a std::vector by constant reference unless you must. Pass a std::span (or gsl::span pre-C++20) by value instead.
   See "What is a "span" and when should I use one? " for more details.

3. You should use a type for dense matrices. Not only would it be more semantic, but also far more efficient.

   A vector-of-vectors is far more amorph, backed by many independent allocations, and using far more expensive indirection. Thus, you cannot efficiently read an arbitrary cell, or move from cell to cell.

   There are many matrix-classes even on this site, and some are sufficient.

4. For passing the coordinate-pair x and y you could use a dedicated point-class, or a std::pair. If you unclutter the rest, one can justify passing them separately though.

5. Making the caller allocate your scratch space causes all kinds of headaches and inconvenience, aside from being a bad break of proper abstraction. Desist from burdening the caller.

6. If you pass a string just for reading it, and it doesn't have to be nul-terminated, pass a std::string_view by value, not a std::string by constant reference. It's more efficient and versatile.

7. Passing a string for selecting a mode is such a scripting thing to do. In C++, if a bool is insufficiently explicit, we use an enum. Much more efficient and type-safe, especially if it's an enum-class.

• watch-this: 1. It's my fault, it's not the main file, I just added main() for posting it here, I have it separately on my laptop. 2. Why I shouldn't pass a vector by reference? and what is std::span? 3. did not get what you mean 4. should I use a std::pair or shouldn't I? 5.What's the proper way? I need you to ellaborate on most of the points if possible.
• Deduplicator: Elaborated most. Re 5: If not the caller, there is only the callee.

Answer 4

I'd make

 def _get_possible_moves(self, x, y):
 possible_moves = []
 if x < self.end_x:
 possible_moves.append([x + 1, y])
 if y < self.end_y:
 possible_moves.append([x, y + 1])
 return possible_moves

a generator:

 def _get_possible_moves(self, x, y):
 if x < self.end_x:
 yield x + 1, y
 if y < self.end_y:
 yield x, y + 1