loading...

Daily Coding Challenge #20

wingkwong profile image Wing-Kam ・5 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 - Maximum Product of Two Elements in an Array

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).


Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 
Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.
Example 3:

Input: nums = [3,7]
Output: 12


Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3
*/

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // find the biggest number x & the second biggest number y
        // return (x-1)*(y-1)
        sort(nums.rbegin(),nums.rend());
        return (nums[0]-1)*(nums[1]-1);
    }
};

/*
LeetCode - Check If a String Contains All Binary Codes of Size K

Given a binary string s and an integer k.

Return True if all binary codes of length k is a substring of s. Otherwise, return False.



Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.
Example 2:

Input: s = "00110", k = 2
Output: true
Example 3:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring. 
Example 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.
Example 5:

Input: s = "0000000001011100", k = 4
Output: false
*/


class Solution {
public:
    bool hasAllCodes(string s, int k) {
        // sliding window approach
        int n=(int)s.size();
        set<string> ss;
        for(int i=0;i<n-k+1;i++){
            // put all k-size substring to a set
            ss.insert(s.substr(i,k));
        }
        // and compare if it has the same as 2^k
        return ss.size()==pow(2,k);
    }
};

// TLE
// class Solution {
// public:
//     bool hasAllCodes(string s, int k) {
//         string zero(k,'0');
//         if(s.find(zero)==string::npos) return false;
//         for(int i=1;i<pow(2,k);i++){
//             string ss=bitset<20>(i).to_string().substr(20-k,k);
//             if(s.find(ss)==string::npos) return false;
//         }
//         return true;
//     }
// };

/*
LeetCode - Course Schedule IV

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

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

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that if course a is a prerequisite of course b and course b is a prerequisite of course c, then, course a is a prerequisite of course c.



Example 1:


Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.
Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites and each course is independent.
Example 3:


Input: n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]
Example 4:

Input: n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
Output: [false,true]
Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]
*/

class Solution {
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        // Using Floyd Warshall Algorithm
        //---------------------------------
        // Applications:
        // To find the shortest path is a directed graph
        // To find the transitive closure of directed graphs
        // To find the Inversion of real matrices
        // For testing whether an undirected graph is bipartite
        //---------------------------------
        // Time : O(n^3) 
        // Space: O(n^2) 
        //---------------------------------
        // n = no of vertices
        // A = matrix of dimension n*n
        // for k = 1 to n
        //     for i = 1 to n
        //         for j = 1 to n
        //             Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
        // return A
        vector<bool> ans;
        vector<vector<bool>> c(n,vector<bool>(n,false));
        for(auto& p:prerequisites) c[p[0]][p[1]]=true;
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    c[i][j]=c[i][j]||(c[i][k]&&c[k][j]);
                    // or if (c[i][k]+c[k][j]<c[i][j]) c[i][j]=c[i][k]+c[k][j];  
                }
            }
        }
        for(auto& q:queries) ans.push_back(c[q[0]][q[1]]);
        return ans;
    }
};

class Solution2 {
public:
    bool helper(int u, int v){
        // base case. if v is reachable from u, return true
        if(u==v) return true;
        // a queue for bfs
        list<int> q;
        // set the current node as "visited"
        vis[u]=1;
        // enqueue the current node 
        q.push_back(u);
        while(!q.empty()){
            // dequeue a vertex 
            u=q.front();
            q.pop_front();
            // get all adjacent vertices of u
            for(auto lt=g[u].begin();lt!=g[u].end();lt++){
                // if it is v, that means it is reachable, return true
                if(*lt==v) return true;
                // if it is not visited
                if(!vis[*lt]){
                    // mark it as visited 
                    vis[*lt]=1;
                    // and put it to the queue
                    q.push_back(*lt);
                }
            }
        }
        // cannot be reachable
        return false;
    }

    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        // BFS Approach
        vector<bool> ans;
        g.resize(n);
        vis.assign(n,0);
        for(auto& p:prerequisites) g[p[0]].push_back(p[1]);
        for(auto q:queries){
           if(helper(q[0],q[1])) ans.push_back(true);
            else ans.push_back(false);
            vis.assign(n,0);
        }

        return ans;
    }
private:
    vector<vector<int>> g;
    vector<int> vis;
};

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