# Daily Coding Challenge #20

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!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

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