# Daily Coding Challenge #122

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.

/*
Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
*/

class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
// handle three cases
// the new interval is in the rnage of other interval
// the new interval comes before the other interval
// the new interval comes after the other interval
vector<vector<int>> ans;
for(int i=0;i<intervals.size();i++){
if(intervals[i]<newInterval) ans.push_back(intervals[i]);
else if(intervals[i]>newInterval){
ans.push_back(newInterval);
newInterval=intervals[i];
} else if(intervals[i]>=newInterval||intervals[i]<=newInterval){
newInterval=min(newInterval, intervals[i]);
newInterval=max(newInterval, intervals[i]);

}
}
ans.push_back(newInterval);
return ans;
}
};


/*
Special Positions in a Binary Matrix

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],
[0,0,1],
[1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat == 1 and all other elements in row 1 and column 2 are 0.
Example 2:

Input: mat = [[1,0,0],
[0,1,0],
[0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.
Example 3:

Input: mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
Output: 2
Example 4:

Input: mat = [[0,0,0,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
Output: 3

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 1.
*/

class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
// row[i] stores how many 1s in row i
// col[j] stores how many 1s in col j
int row={0}, col={0};
for(int i=0;i<mat.size();i++){
for(int j=0;j<mat[i].size();j++){
if(mat[i][j]==1) {
row[i]++;
col[j]++;
}
}
}
int ans=0;
for(int i=0;i<mat.size();i++){
for(int j=0;j<mat[i].size();j++){
// increase ans only when mat[i][j] is one
// and it is the only 1 in the row i and col j
if(mat[i][j]==1&&row[i]==1&&col[j]==1){
ans++;
}
}
}
return ans;
}
};


/*
Count Unhappy Friends

You are given a list of preferences for n friends, where n is always even.

For each person i, preferences[i] contains a list of friends sorted in the order of preference. In other words, a friend earlier in the list is more preferred than a friend later in the list. Friends in each list are denoted by integers from 0 to n-1.

All the friends are divided into pairs. The pairings are given in a list pairs, where pairs[i] = [xi, yi] denotes xi is paired with yi and yi is paired with xi.

However, this pairing may cause some of the friends to be unhappy. A friend x is unhappy if x is paired with y and there exists a friend u who is paired with v but:

x prefers u over y, and
u prefers x over v.
Return the number of unhappy friends.

Example 1:

Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
Output: 2
Explanation:
Friend 1 is unhappy because:
- 1 is paired with 0 but prefers 3 over 0, and
- 3 prefers 1 over 2.
Friend 3 is unhappy because:
- 3 is paired with 2 but prefers 1 over 2, and
- 1 prefers 3 over 0.
Friends 0 and 2 are happy.
Example 2:

Input: n = 2, preferences = [, ], pairs = [[1, 0]]
Output: 0
Explanation: Both friends 0 and 1 are happy.
Example 3:

Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
Output: 4

Constraints:

2 <= n <= 500
n is even.
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] does not contain i.
All values in preferences[i] are unique.
pairs.length == n/2
pairs[i].length == 2
xi != yi
0 <= xi, yi <= n - 1
Each person is contained in exactly one pair.
*/

class Solution {
public:
int ans=0;
vector<vector<int>> pos;
map<int, int> m;
void calc(vector<vector<int>>& preferences, int p, int target){
for(int pref: preferences[p]){
if(pref==target) return;
if(pos[pref][p]<pos[pref][m[pref]]) {
ans++;
return;
}
}
}
int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
for(auto pair: pairs){
m[pair]=pair;
m[pair]=pair;
}
pos=vector<vector<int>>(n, vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
pos[i][preferences[i][j]]=j;
}
}
for(auto pair: pairs){
calc(preferences, pair,pair);
calc(preferences, pair,pair);
}
return ans;

}
};


There are other programming solutions in the following repositories below. Star and watch for timely updates!

## wingkwong / competitive-programming

### Discussion   