# Daily Coding Challenge #21

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)*(nums-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-1)*(nums-1);
}
};
``````

``````/*
LeetCode - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:
Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:
Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = 
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.
Example 3:

Input: h = 5, w = 4, horizontalCuts = , verticalCuts = 
Output: 9

Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.
*/

class Solution {
public:
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
// Approach: Find the max gap between each horizontal cuts and vertical cuts
const long long M=1000000007;
// sort horizontalCuts & verticalCuts
sort(horizontalCuts.begin(),horizontalCuts.end());
sort(verticalCuts.begin(),verticalCuts.end());
// declare the size for horizontalCuts and verticalCuts
int m=(int)horizontalCuts.size(), n=(int)verticalCuts.size();
// mh: storing max horizontalCuts gap ; hgap: storing horizontalCuts gap between two horizontal cuts
// mv: storing max verticalCuts gap   ; vgap: storing verticalCuts gap between two vectical cuts
long long mh=horizontalCuts, mv=verticalCuts, hgap, vgap;
for(int i=1;i<m;i++) {
// find out the max horizontalCuts gap
hgap=horizontalCuts[i]-horizontalCuts[i-1];
mh=max(mh,hgap);
}
for(int i=1;i<n;i++) {
// find out the max verticalCuts gap
vgap=verticalCuts[i]-verticalCuts[i-1];
mv=max(mv,vgap);
}
// need to take care of the last case
hgap=h-horizontalCuts[m-1];
vgap=w-verticalCuts[n-1];
mh=max(mh,hgap);
mv=max(mv,vgap);
// the max area is max horizontalCuts gap * max verticalCuts gap
return (int)(mh%M*mv%M);
}
};

// another approach is to use adjacent_difference to find the differences and store them in a vector
// find out mh and mv by using *max_element
``````

``````/*
LeetCode - Reorder Routes to Make All Paths Lead to the City Zero

There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach the city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2:
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Constraints:

2 <= n <= 5 * 10^4
connections.length == n-1
connections[i].length == 2
0 <= connections[i], connections[i] <= n-1
connections[i] != connections[i]
*/

class Solution {
public:
int minReorder(int n, vector<vector<int>>& connections) {
// approach:
// assume all edges need to be reversed
// if the edge is found in set, no need to change.
int ans=(int)connections.size();
set<int> s;
s.insert(0);
for(auto c:connections){
if(s.find(c)!=s.end()) ans--;
s.insert(c);
s.insert(c);
}
return ans;
}
};
``````

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

## wingkwong / atcoder

### Discussion   