class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
// Maps each process to its children
unordered_map<int, vector<int>> children_of_each_process;
for (int i=0; i<ppid.size(); ++i) {
children_of_each_process[ppid[i]].push_back(pid[i]);
}
vector<int> processes_killed;
queue<int> processes_to_kill;
processes_to_kill.push(kill);
while (!processes_to_kill.empty()) {
int process = processes_to_kill.front();
processes_to_kill.pop();
processes_killed.push_back(process);
// Find the children of the process, if any, and add them to the queue
auto it = children_of_each_process.find(process);
if (it != children_of_each_process.end()) {
vector<int> children_of_process = it>second;
for (int i=0; i<children_of_process.size(); ++i) {
processes_to_kill.push(children_of_process[i]);
}
}
}
return processes_killed;
}
};
adpa
@adpa
Posts made by adpa

C++ O(N) Hash table and BFS

RE: Java Solution, Sliding Window
My C++ version with a change in the last loop.
class Solution { public: bool checkInclusion(string s1, string s2) { int len1 = s1.length(), len2 = s2.length(); if (len1 > len2) return false; vector<int> count(26, 0); for (int i=0; i<len1; ++i) { count[s1[i]'a']++; count[s2[i]'a']; } int numZeroes = 0; for (int i=0; i<26; ++i) { if (count[i] == 0) numZeroes++; } if (numZeroes == 26) return true; for (int i=len1; i<len2; ++i) { count[s2[i]'a']; if (count[s2[i]'a'] == 0) numZeroes++; else if (count[s2[i]'a'] == 1) numZeroes; count[s2[ilen1]'a']++; if (count[s2[ilen1]'a'] == 0) numZeroes++; else if (count[s2[ilen1]'a'] == 1) numZeroes; if (numZeroes == 26) return true; } return false; } };

C++ O(NlogN) 86ms with proof
class Solution { public: int arrayPairSum(vector<int>& nums) { // Sorting is O(NlogN) sort(nums.begin(), nums.end()); // The loop is O(N) int sum = 0; for (int i=0; i<nums.size(); i+=2) { sum += nums[i]; } return sum; } }
Proof:
Take the 2n elements and put them into two groups A = {a[1], … , a[n]} and B = {b[1], … b[n]}.
Define S = sum (i from 1 to n) min(a[i], b[i])
For all i, we say that a[i] and b[i] are paired.Our objective: find a grouping of the elements into the sets A and B such that S is maximized. Call the maximal sum Smax.
We can assume that the grouping is such that a[i] <= b[i] for all i so S = sum(i from 1 to n) a[i]
Order the set {a[1], b[1], ..., a[n], b[n]} of 2n elements to get the ordered sequence {d[1], … d[2n]}.
First note that d[2n] is not in the set A, as it is the biggest number so the element with which it is paired will be smaller or equal.
Now suppose d[2n1] is not paired with d[2n]. So d[2n] is paired with an element d[i] such that i<2n1, and d[2n1] is paired with an element d[j] such that j<2n1, with i different from j. So the contribution to the sum S of these two pairs is:
min(d[i], d[2n]) + min(d[j], d[2n1]) = d[i] + d[j]However, suppose that we had instead paired d[i] with d[j], and d[2n] with d[2n1]. Then the contribution to the sum S of these two pairs would be:
min(d[2n1], d[2n]) + min(d[i], d[j]) = d[2n1] + min(d[i], d[j]),
instead of
d[i] + d[j] = max(d[i], d[j]) + min(d[i], d[j]) <= d[2n1] + min(d[i], d[j])
i.e. it would be a bigger or equal contribution. So d[2n1] should be paired with d[2n].We can then reason similarly with all elements d[i] with i<2n1: d[2n2] must be paired with d[2n3], d[2n4] must be paired with d[2n5], etc. We therefore pair all adjacent elements (d[i], d[i+1]), starting from i=1. Only d[i] will contribute to the sum S as it is smaller than or equal to d[i+1], hence our selection algorithm.

RE: C++ 0ms O(N) dynamic programming solution
Thanks for your reply. Your (2) helps but I am not sure about your (1). If nums[i] <= N, then N cannot be nums[i1], because nums[i1] < nums[i] <= N i.e. nums[i1] < N. I've updated the proof.

C++ 0ms O(N) dynamic programming solution
class Solution { public: int wiggleMaxLength(vector<int>& nums) { int size = nums.size(); if (size == 0) { return 0; } /** up[i] is the length of a longest wiggle subsequence of {nums[0],...,nums[i]}, with a positive difference between its last two numbers. This subsequence may or may not include nums[i] and there may be several such subsequences (of the same length). We call this a subsequence of type U. */ vector<int> up(size, 0); /** down[i] is the length of a longest wiggle subsequence of {nums[0],...,nums[i]}, with a negative difference between its last two numbers. This subsequence may or may not include nums[i] and there may be several such subsequences (of the same length). We call this a subsequence of type D. */ vector<int> down(size, 0); // At i=0, there is only one number and we can use it as a subsequence, i.e up[0]=down[0]=1 up[0] = 1; down[0] = 1; for(int i=1; i<size; ++i){ if (nums[i] > nums[i1]) { /** If nums[i] > nums[i1], then we can use nums[i] to make a longer subsequence of type U Proof: We consider a subsequence of type D in {0,...,i1} (its length is down[i1]). Let N be the last number of this subsequence.  If nums[i] > N, then we can add nums[i] to the subsequence and it gives us a longer valid subsequence of type U.  If nums[i] <= N, then: (1) N cannot be nums[i1], because nums[i1] < nums[i] <= N i.e. nums[i1] < N (2) We can replace N with nums[i1] (we still have a valid subsequence of type D since N >= nums[i] > nums[i1] i.e. N > nums[i1]), and then add nums[i] to the subsequence, and we have a longer subsequence of type U. Therefore up[i] = down[i1] + 1 There is no gain in using nums[i] to make a longer subsequence of type D. Proof: Let N be the last number of a subsequence of type U in {0,...,i1}. Assume we can use nums[i] to make a longer subsequence of type D. Then: (1) N cannot be nums[i1], otherwise we would not be able to use nums[i] to make a longer subsequence of type D as nums[i] > nums[i1] (2) Necessarily nums[i] < N, and therefore nums[i1] < N since nums[i1] < nums[i]. But this means that we could have used nums[i1] already to make a longer subsequence of type D. So even if we can use nums[i], there is no gain in using it, so we keep the old value of down (down[i] = down[i1]) */ up[i] = down[i1] + 1; down[i] = down[i1]; } else if (nums[i] < nums[i1]) { /** The reasoning is similar if nums[i] < nums[i1] */ down[i] = up[i1] + 1; up[i] = up[i1]; } else { /** if nums[i] == nums[i1], we cannot do anything more than what we did with nums[i1] so we just keep the old values of up and down */ up[i] = up[i1]; down[i] = down[i1]; } } return max(up[size1], down[size1]); } };

C++ O(N) solution
class Solution { public: vector<vector<int>> findLeaves(TreeNode* root) { vector<vector<int>> res; int height = findHeight(root, res); return res; } int findHeight(TreeNode* node, vector<vector<int>>& res) { if (!node) { return 1; } int leftHeight = findHeight(node>left, res); int rightHeight = findHeight(node>right, res); int height = 1 + max(leftHeight, rightHeight); if (res.size() <= height) { vector<int> vec(1, node>val); res.push_back(vec); } else { res[height].push_back(node>val); } return height; } };

C++ solution
class Solution { public: /** count(n): all the numbers with n distinct digits (does not include 0 for n=1) countNumbersWithUniqueDigits(n): all the numbers x with distinct digits, such that x < 10^n */ int countNumbersWithUniqueDigits(int n) { if (n==0) return 1; // corresponds to the number 0 return count(n)+countNumbersWithUniqueDigits(n1); } int count(int n) { // We cannot have a number with more than 10 distinct digits if (n>10) return 0; /** For the first digit, choose one of {1,...,9}, i.e. we have res=9 choices. We cannot choose 0 as the first digit For the second digit, choose one of {0,...,9}  excluding the first digit, i.e. we have 9 choices. For the third digit, we have 8 choices (all digits except the first and second). For the fourth digit, we have 7 choices. etc. */ int res = 9; int num = 9; for (int i=1; i<n; ++i) { res*=num; num; } return res; } };

8ms C++ solution using sorting
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { if (nums1.empty()  nums2.empty()) { return vector<int>(); } sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); return nums2[0] < nums1[0] ? intersection2(nums1, nums2) : intersection2(nums2, nums1); } vector<int> intersection2(vector<int>& nums1, vector<int>& nums2) { vector<int> res; size_t pos1 = 0; size_t pos2 = 0; size_t size1 = nums1.size(); size_t size2 = nums2.size(); while (true) { while (pos2 < size2 && nums2[pos2] < nums1[pos1]) { ++pos2; } if (pos2 == size2) { break; } if (nums2[pos2] == nums1[pos1]) { res.push_back(nums2[pos2++]); while (pos2 < size2 && nums2[pos2]==nums2[pos21]) { // Move forward if we have duplicates ++pos2; } } ++pos1; while (pos1 < size1 && nums1[pos1]==nums1[pos11]) { // Move forward if we have duplicates ++pos1; } if (pos1 == size1) { break; } } return res; } };
For Intersection of Two Arrays II, we just need to remove the two while loops where we move forward in the case of duplicates

28ms C++ solution with BFS
This solution is based on another that I found in the forum, I changed a few things.
class Solution { public: int shortestDistance(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); // total will be filled with the sum of the distances of every reachable empty land from all buildings vector<vector<int>> total(rows, vector<int>(cols, 0)); /** From the first building we find, we will try to reach all 0 lands (i.e. empty) and we will make them 1 in grid Then from the second building we find, we will try to reach all 1 lands (i.e. empty and reachable from the previously found building) and we will make them 2 in grid ... For the n'th building we find, we will try to reach all (n1) lands (i.e. empty and reachable from all the previously found buildings) and we will make them n etc. */ array<int, 5> dir = {0,1,0,1,0}; // number of the building we are currently examining. We decrease the variable by 1 each time we finish examining a building. int buildingNumber = 0; for (int i=0; i<rows; ++i) { for (int j=0; j<cols; ++j) { if (grid[i][j] == 1) { // distances will be filled with the distance of every reachable empty land from this specific building vector<vector<int>> distances(rows, vector<int>(cols, 0)); queue<pair<int,int>> q; pair<int,int> p(i,j); q.push(p); while (!q.empty()) { pair<int,int> p2 = q.front(); q.pop(); int old_x = p2.first; int old_y = p2.second; for (int k=0; k<4; ++k) { int new_x = old_x+dir[k]; int new_y = old_y+dir[k+1]; if (new_x>=0 && new_x<rows && new_y>=0 && new_y<cols && grid[new_x][new_y]==buildingNumber) { distances[new_x][new_y] = distances[old_x][old_y]+1; total[new_x][new_y] += distances[new_x][new_y]; pair<int,int> p3(new_x, new_y); q.push(p3); grid[new_x][new_y]; } } } buildingNumber; } } } int min_dist = INT_MAX; for (int i=0; i<rows; ++i) { for (int j=0; j<cols; ++j) { // We are only interested in empty lands that are reachable from all buildings if (grid[i][j]==buildingNumber) { min_dist = min(min_dist, total[i][j]); } } } return min_dist == INT_MAX ? 1 : min_dist; } };

144ms C++ solution with BFS
class Solution { public: void wallsAndGates(vector<vector<int>>& rooms) { queue<pair<int,int>> q; int rows = rooms.size(); if (rows == 0) return; int cols = rooms[0].size(); // Add the (i,j) coordinate of every gate to the queue for (int i=0; i<rows; ++i) { for (int j=0; j<cols; ++j) { pair<int, int> p(i, j); if (rooms[i][j]==0) { q.push(p); } } } array<int, 5> dir = {0, 1, 0, 1, 0}; // Breadth first search while (!q.empty()) { pair<int,int> p = q.front(); q.pop(); // For every element in the queue, try to move in all four directions (east, north, west, south) for (int k=0; k<4; ++k) { // Coordinates of the old position int old_i = p.first; int old_j = p.second; // Coordinates of the new position int new_i = old_i+dir[k]; int new_j = old_j+dir[k+1]; /** If the new position is still within the boundaries of rooms (the first four conditions of the if statement), and if the new position corresponds to an empty room (rooms[new_i][new_j]==INT_MAX), then update rooms[new_i][new_j] to be rooms[old_i][old_j]+1 (= distance of the old position to the nearest gate + 1). Then add the coordinates of the new position to the queue. */ if (new_i>=0 && new_i<rows && new_j>=0 && new_j<cols && rooms[new_i][new_j]==INT_MAX) { rooms[new_i][new_j] = rooms[old_i][old_j]+1; pair<int,int> p2(new_i, new_j); q.push(p2); } } } } };