Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 19

Description

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 {
public:
  int minFallingPathSum(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix.front().size();
    for(int i = 1; i < rows; ++i) {
      for(int j = 0; j < cols; ++j) {
        int lastSum = INT_MAX;
        for(int k = max(0, j - 1); k < min(cols, j + 2); ++k) {
          lastSum = min(lastSum, matrix[i - 1][k]);
        }
        matrix[i][j] += lastSum;
      }
    }
    return *min_element(matrix.back().begin(), matrix.back().end());
  }
};

// Accepted
// 50/50 cases passed (14 ms)
// Your runtime beats 45.08 % of cpp submissions
// Your memory usage beats 5.08 % of cpp submissions (12.4 MB)