# Daily Coding Challenge #24

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 - Two City Scheduling

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:

1 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000
*/

class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
// sort by the diff
// ------------------------------------------
// [[10,20],[30,200],[400,50],[30,20]]
// -10, -170, 350, 10
// -170, -10, 10, 350
sort(costs.begin(),costs.end(),[](vector<int>& a, vector<int>& b){
return a[0]-b[0] < a[1]-b[1];
});
// another approach is to use nth_element to achieve O(n log n) runtime
// becuase we don't need to care much about the exact order,
// just find the middle as a pivot and split into two groups
// --------------------------------APPROACH 2-------------------------------------------------
// nth_element(begin(cs), begin(cs) + cs.size() / 2, end(cs), [](vector<int> &a, vector<int> &b) {
//     return (a[0] - a[1] < b[0] - b[1]);
// });
// --------------------------------APPROACH 2-------------------------------------------------
int ans=0, n=(int)costs.size();
// it is guaranteed that costs.length is even
// hence, the first half goes to city A, the second half goes to city B
for(int i=0;i<n/2;i++) ans+=costs[i][0]+costs[i+n/2][1];
return ans;
}
};

``````

``````/*
LeetCode - K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000
*/

class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
// we don't need to care about the exact order
// nth_element approach should be enough
nth_element(points.begin(),points.begin()+K,points.end(),[](vector<int>& a, vector<int>& b){
// sort by Euclidean distance
// dist(q,p) = sqrt( (q1-p1)*(q1-p1) + (q2-p2)*(q2-p2) )
// since we are comparing the points with the origin (0,0)
// dist(q,p) = sqrt( (q1)*(q1) + (q2)*(q2) )
// and we don't need to perform sqrt as sqrt(a) must be smaller than sqrt(b) if a < b
return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
});
// resize points to show K clostest points
points.resize(K);
return points;
}
};
``````

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.