Daily Coding Challenge #114

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.

/*
Repeated Deletion
https://binarysearch.io/problems/Repeated-Deletion

Given a string s, repeatedly delete the earliest consecutive duplicate characters.

Constraints

n ≤ 100,000 where n is the length of s.
Example 1
Input

s = "abbbaac"
Output

"c"
Explanation

"bbb" are the earliest consecutive duplicate characters which gets deleted. So we have "aaac".
"aaa" then gets deleted to end up with "c".
*/

#include "solution.hpp"
using namespace std;

class Solution {
public:
string solve(string s) {
string st;
st.push_back(s[0]);
int i=1;
// stack approach
// if the current char match the previous one, look for the next which doesnt match
// else push the current char and increase i
// keep iterating it until i being out of bound
while(i<s.size()){
int j=i;
while(s[j]==st.back()&&j<s.size()) j++;
if(i==j) st.push_back(s[i++]);
else {
st.pop_back();
i=j;
}
}
return st;
}
};



/*
Flipped-Matrix
https://binarysearch.io/problems/Flipped-Matrix

You are given a two-dimensional integer matrix containing 0 and 1. For any row or column in the matrix you can toggle all the bits such that all the 1s become 0 and all the 0s become 1.

Given you can make any number of these operations, and that we treat each row as a binary number, return the largest sum that can be made of these numbers.

Constraints

n, m ≤ 30 where n and m are the number of rows and columns in matrix.
Example 1
Input

matrix = [
[0, 0, 1],
[0, 0, 0]
]
Output

13
Explanation

If we flip both rows we get

[1, 1, 0]
[1, 1, 1]
In binary these are 6 and 7 and their sum is 13.
*/

#include "solution.hpp"
using namespace std;

class Solution {
public:
int solve(vector<vector<int>>& matrix) {
/*
To achieve the maximum sum, the leftmost column must be all 1s.
Therefore, we check if matrix[i][0] is 0 first. If so, flip the whole row simply by using xor.
We need to store how many 1s in each column. The number of 1s in the first column must be the number of row. Hence, v[0]=m;
Then, for each column starting from the second one, we check if the number of 0s is greater than that of 1s / 2.
If so, that means we need to flip the whole column.
However, we don't actually need to flip it because we just wanna know the number of 1s.
Therefore, it is either zero (flip all 0s to 1s), or m-zero (no need to flip).
The last part is to calculate the sum. Starting from the rightmost digit, we just need to multiple by 1,2,4,8... as this is a binary number.
*/
int m=matrix.size(), n=matrix[0].size(), ans=0;
for(int i=0;i<m;i++) {
if(matrix[i][0]==0) {
for(int j=0;j<n;j++) {
matrix[i][j]^=1;
}
}
}
vector<int> v(n,0);
v[0]=m;
for(int j=1;j<n;j++) {
int cnt=0, zero=0;
for(int i=0;i<m;i++)zero+=matrix[i][j]==0;
if(zero>(m/2)) v[j]=zero;
else v[j]=m-zero;
}
int p=1;
for(int i=v.size()-1;i>=0;i--){
ans+=p*v[i];
p*=2;
}
return ans;
}
};



/*
All Elements in Two Binary Search Trees
https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]
Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]
Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]
Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]
Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

Each tree has at most 5000 nodes.
Each node's value is between [-10^5, 10^5].
*/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> ans;
void traverse(TreeNode* root){
if(!root) return;
traverse(root->left);
traverse(root->right);
ans.push_back(root->val);
}

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
// Traverse the first tree in list1 and the second tree in list2.
// Merge the two trees in one list and sort it.
traverse(root1);
traverse(root2);
sort(ans.begin(), ans.end());
return ans;
}
};


/*
Connected Cities
https://binarysearch.io/problems/Connected-Cities

You are given n cities represented as an integer in [0, n) and a list of one-way roads that connects one city to another.

Return whether you can reach any city from any city.

Example 1
Input

n = 2
[0, 1],
[1, 0]
]
Output

true
Explanation

You can go 0 to 1 and 1 to 0

Example 2
Input

n = 2
[1, 0]
]
Output

false
Explanation

You can go 1 to 0 but not 0 to 1
*/

#include "solution.hpp"
using namespace std;

class Solution {
public:
vector<vector<int>> g, gr;
vector<int> vis;
int cnt;

void dfs(int u, vector<vector<int>>& g){
vis[u]=1;
cnt++;
for(int v: g[u]){
if(!vis[v]){
dfs(v,g);
}
}
}

bool ok(vector<vector<int>>& g, int n){
vis.assign(n,0);
cnt=0;
dfs(0,g);
return cnt==n;
}

bool solve(int n, vector<vector<int>>& roads) {
// Return whether you can reach any city **from any city**.
// idea: dfs the whole path to see if the count is same as n
// you can also solve this question with kosaraju's algorithm
// but you will need 2 dfs functions and a stack
if(n==0) return true;
g.resize(n), gr.resize(n);
return ok(g,n)&&ok(gr,n);
}
};



/*
Missing Numbers from 1 to N
https://binarysearch.io/problems/Missing-Numbers-from-1-to-N

You are given a list of integers nums of length n where all numbers in the list are from [1, n] and some elements appear twice while others only once. Return all the numbers from [1, n] that are not in the list, sorted in ascending order.

Can you do it in \mathcal{O}(n)O(n) time, modify nums in-place and use \mathcal{O}(1)O(1) additional space?

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input

nums = [3, 3, 1, 1, 5, 5]
Output

[2, 4, 6]
Explanation

The numbers [2, 4, 6] are missing from [1, 6]
*/

#include "solution.hpp"
using namespace std;

class Solution {
public:
vector<int> solve(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n;i++){
int num = nums[i];
while(num>0&&num<=n&&nums[num-1]!=num){
swap(nums[num-1], num);
}
}
vector<int> ans;
for(int i=0;i<n;i++){
if(nums[i]!=i+1) ans.push_back(i+1);
}
return ans;
}
};



/*
Column-Sort
https://binarysearch.io/problems/Column-Sort

Given a two-dimensional integer matrix, sort each of the columns in ascending order.

Example 1
Input

matrix = [
[10, 20, 30],
[5, 5, 3],
[0, 10, 7]
]
Output

[
[0, 5, 3],
[5, 10, 7],
[10, 20, 30]
]
*/

#include "solution.hpp"
using namespace std;

class Solution {
public:
vector<vector<int>> solve(vector<vector<int>>& matrix) {
int m=matrix.size(), n=matrix[0].size();
vector<int> cols;
vector<vector<int>> ans = matrix;
// extract each column, sort it in ascending order
// put it back to the right place
for(int col=0;col<n;col++){
for(int row=0;row<m;row++) cols.push_back(matrix[row][col]);
sort(cols.begin(), cols.end());
for(int row=0;row<m;row++) ans[row][col]=cols[row];
cols.clear();
}
return ans;
}
};



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

wingkwong / competitive-programming

Posted on by:

Wing-Kam

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