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);
}

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).

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.

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