loading...

Daily Coding Challenge #70

wingkwong profile image Wing-Kam ・6 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 - Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.


Constraints:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5
*/

// Topological Sorting

// This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
// Topological sort could also be done via BFS.


// BFS approach
// simplified version of Solution 3 
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses), bfs;
        vector<vector<int>> g(numCourses);
        for(auto& p:prerequisites) {
            g[p[0]].push_back(p[1]);
            indegree[p[1]]++;
        }

        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) bfs.push_back(i);
        }

        for(int i=0;i<bfs.size();i++){
            for(int j:g[bfs[i]]){
                if(--indegree[j]==0) bfs.push_back(j);
            }
        }
        return bfs.size()==numCourses;
    }
};

// DFS approach
class Solution2 {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        g.resize(numCourses);
        c.assign(numCourses,0);
        for(auto& p:prerequisites)  g[p[0]].push_back(p[1]);

        for(int i=0;i<numCourses;i++){
            if(c[i]==0) {
                if(!dfs(i)) return false;
            }
        }
        return true;
    }
private:
    vector<vector<int>> g;
    vector<int> c;
    bool dfs(int u){
        if(c[u]==2) return true;
        c[u]=1;
        for(auto v:g[u]){
            if(c[v]==2) continue;
            if(c[v]==1||!dfs(v)) return false;
        }
        c[u]=2;
        return true;
    }
};


// using Kahn’s algorithm
// L ← Empty list that will contain the sorted elements
// S ← Set of all nodes with no incoming edge

// while S is not empty do
//     remove a node n from S
//     add n to tail of L
//     for each node m with an edge e from n to m do
//         remove edge e from the graph
//         if m has no other incoming edges then
//             insert m into S

// if graph has edges then
//     return error   (graph has at least one cycle)
// else 
//     return L   (a topologically sorted order)
class Solution3 {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses);
        vector<vector<int>> g;
        g.resize(numCourses);
        for(auto& p:prerequisites) g[p[0]].push_back(p[1]);
        for(int i=0;i<numCourses;i++){
            for(auto lt=g[i].begin();lt!=g[i].end();lt++){
                indegree[*lt]++;
            }
        }
        queue<int> q;
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) q.push(i);
        }
        int cnt=0;
        while(!q.empty()){
            // if you wanna see the result, use another vector to push_back u
            int u=q.front();
            q.pop();
            for(auto lt=g[u].begin();lt!=g[u].end();lt++){
                if(--indegree[*lt]==0) q.push(*lt);
            }
            cnt++;
        }
        return cnt==numCourses;
    }
};

class Solution4 {
public:
    bool canFinish(int n, vector<vector<int>>& p) {
        vector<vector<int>> g(n);
        vector<int> indegree(n,0);
        for(auto x:p){
            g[x[1]].push_back(x[0]);
            indegree[x[0]]++;
        }
        for(int i=0;i<n;i++){
            int j;
            for(j=0;j<n;j++){
                if(indegree[j]==0) break;
            }
            if(j==n) return false;
            indegree[j]--;
            for(auto to:g[j]){
                indegree[to]--;
            }
        }
        return true;
    }
};

/*
LeetCode - Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .
Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
*/

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses,0);
        vector<int> ans;
        for(auto p:prerequisites) {
            // build the graph
            graph[p[1]].push_back(p[0]);
            // cnt indegree
            indegree[p[0]]++;
        }
        for(int i=0;i<numCourses;i++){
            int j=0;
            // search for the index j where indegree[j] = 0
            for(;j<numCourses;j++){
                if(indegree[j]==0){
                    break;
                }
            }
            // return {} if no such result
            if(j==numCourses) return {};
            // deduct indegree[j] by 1 so that it won't be visited again
            indegree[j]--;
            // reduce the in-degree of each neighbor by 1
            for(auto to:graph[j]) {
                indegree[to]--;
            }
            // store the ans
            ans.emplace_back(j);
        }
        return ans;
    }
};

/*
LeetCode - 01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]
Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]


Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.
*/

class Solution {
public:
    int dfs(vector<vector<int>>& matrix, int i, int j){
        if(i<0||i>matrix.size()-1||j<0||j>matrix[0].size()-1||matrix[i][j]==-1) return 10000;
        if(matrix[i][j]==0||matrix[i][j]==1) {
            return matrix[i][j];
        }
        int d = matrix[i][j];
        // -1 : visited
        matrix[i][j]=-1;
        d = min({
            d,
            dfs(matrix,i+1,j)+1,
            dfs(matrix,i-1,j)+1,
            dfs(matrix,i,j+1)+1,
            dfs(matrix,i,j-1)+1
        });
        // inplace update
        matrix[i][j]=d;
        return  d;
    }

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        // approach: dfs inplace 
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                // The number of elements of the given matrix will not exceed 10,000.
               if(matrix[i][j]==1) matrix[i][j]=10000;
            }
        }

        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                dfs(matrix,i,j);
            }
        }
        return matrix;
    }
};

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

markdown guide