Daily Coding Challenge #47

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.

``````/*
Path Crossing

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return True if the path crosses itself at any point, that is, if at any time you are on a location you've previously visited. Return False otherwise.

Example 1:

Input: path = "NES"
Output: false
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

1 <= path.length <= 10^4
path will only consist of characters in {'N', 'S', 'E', 'W}
*/

class Solution {
public:
bool isPathCrossing(string path) {
unordered_map<int,unordered_map<int, int>> m;
int x=0,y=0;
// origin point
m[x][y]=1;
for(char c:path){
if(c=='N') y+=1;
else if(c=='E') x+=1;
else if(c=='S') y-=1;
else if(c=='W') x-=1;
// check if it s visited
if(m[x][y]) return true;
// if not, set it visited
m[x][y]=1;
}
return false;
}
};
``````

``````/*
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];
}
};
``````

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

wingkwong / atcoder

Posted on by:

Wing-Kam

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