loading...

Daily Coding Challenge #19

wingkwong profile image Wing-Kam ・4 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
LeetCode - Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?


Above is a 7 x 3 grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:

Input: m = 7, n = 3
Output: 28


Constraints:

1 <= m, n <= 100
It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.
*/


class Solution {
public:
    int uniquePaths(int m, int n) {
        // store how many ways to reach arr[m][n]
        int dp[m][n];
        // for col=0, there is only one way to reach 
        for(int i=0;i<m;i++) dp[i][0]=1;
        // for row=0, there is only one way to reach
        for(int j=0;j<n;j++) dp[0][j]=1;
        // traverse the rest of the cells
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // since the possible move is either from the top and from the left 
                // so combine them together : dp[i-1][j] (from the top) +  dp[i][j-1] (from the left)
                dp[i][j]= dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};


/*
LeetCode - Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
*/

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // similiar to 62 - Unique Paths 
        int m=obstacleGrid.size(), n=obstacleGrid[0].size();
        int dp[m][n];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<m;i++) {
            if(obstacleGrid[i][0]!=1) dp[i][0]=1;
            // if obstacleGrid[i][0]==1, there is no way to reach row i..m 
            else break;
        }
        for(int j=0;j<n;j++) {
            if(obstacleGrid[0][j]!=1) dp[0][j]=1;
            // if obstacleGrid[0][j]==1, there is no way to reach col j..m 
            else break;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // if it is an obstacle, dp[i][j] is 0
                // only sum for cells without obstacles
                if(!obstacleGrid[i][j]) {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

/*
LeetCode - 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:

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<int> cur(m,grid[0][0]);
        for (int i=1;i<m;i++) cur[i]=cur[i-1]+grid[i][0]; 
        for (int j=1; j<n;j++) {
            cur[0]+=grid[0][j]; 
            for (int i=1; i<m; i++)
                cur[i] = min(cur[i-1],cur[i])+grid[i][j];
        }
        return cur[m-1];
    }
};

class Solution2 {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.size()==0) return 0;
        int m=grid.size();
        int n=grid[0].size();
        int dp[m][n];
        memset(dp,0,sizeof(dp[0][0])*m*n);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j]+=grid[i][j];
                if(i>0&&j>0) {
                    dp[i][j]+=min(dp[i-1][j], dp[i][j-1]);
                } else if(i>0){
                    dp[i][j]+=dp[i-1][j]; // take from the top
                } else if(j>0){
                    dp[i][j]+=dp[i][j-1]; // take from the left
                }
            }
        }
        return dp[m-1][n-1];
    }
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide