2023-03-27 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

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

March LeetCoding Challenge 27

Description

Minimum Path Sum

Given a m x 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:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int minPathSum(vector<vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid.front().size();
    int dp[2][cols];
    for(int i = 0; i < cols; ++i) {
      dp[0][i] = grid[0][i];
      if(i) dp[0][i] += dp[0][i - 1];
    }
    for(int i = 1; i < rows; ++i) {
      int parity = (i & 1);
      dp[parity][0] = dp[!parity][0] + grid[i][0];
      for(int j = 1; j < cols; ++j) {
        dp[parity][j] = min(dp[!parity][j], dp[parity][j - 1]) + grid[i][j];
      }
    }
    return dp[!(rows & 1)][cols - 1];
  }
};

// Accepted
// 61/61 cases passed (3 ms)
// Your runtime beats 99.49 % of cpp submissions
// Your memory usage beats 82.48 % of cpp submissions (9.7 MB)
Algorithm