loading...

Daily Coding Challenge #47

wingkwong profile image Wing-Kam ・3 min read

Daily Coding Challenge (55 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 53 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55

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.


/*
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!

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 πŸ†

Daily Coding Challenge (55 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 53 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55

Posted on Jun 30 by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide