Huahua’s Tech Road

花花酱 LeetCode 2206. Divide Array Into Equal Pairs

By zxi on March 21, 2022

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

Each element belongs to exactly one pair.
The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

nums.length == 2 * n
1 <= n <= 500
1 <= nums[i] <= 500

Solution: Hashtable

Each number has to appear even numbers in order to be paired. Count the frequency of each number, return true if all of them are even numbers, return false otherwise.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool divideArray(vector<int>& nums) {

unordered_map<int, int> m;

for (int num : nums)

++m[num];

return all_of(begin(m), end(m), [](const auto& e) { return e.second % 2 == 0; });

}

};

花花酱 LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph

By zxi on March 11, 2022

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph.

Return a list answer, where answer[i] is the list of ancestors of the i^th node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Example 1:

Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

Constraints:

1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= from_i, to_i <= n - 1
from_i != to_i
There are no duplicate edges.
The graph is directed and acyclic.

Solution: DFS

For each source node S, add it to all its reachable nodes by traversing the entire graph.
In one pass, only traverse each child node at most once.

Time complexity: O(VE)
Space complexity: (V+E)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {

vector<vector<int>> ans(n);

vector<vector<int>> g(n);

for (const auto& e : edges)

g[e[0]].push_back(e[1]);

function<void(int, int)> dfs = [&](int s, int u) -> void {

for (int v : g[u]) {

if (ans[v].empty() || ans[v].back() != s) {

ans[v].push_back(s);

dfs(s, v);

}

};

for (int i = 0; i < n; ++i)

dfs(i, i);

return ans;

}

};

花花酱 LeetCode 2190. Most Frequent Number Following Key In an Array

By zxi on March 11, 2022

You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.

For every unique integer target in nums, count the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:

0 <= i <= nums.length - 2,
nums[i] == key and,
nums[i + 1] == target.

Return the target with the maximum count. The test cases will be generated such that the target with maximum count is unique.

Example 1:

Input: nums = [1,100,200,1,100], key = 1
Output: 100
Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key.
No other integers follow an occurrence of key, so we return 100.

Example 2:

Input: nums = [2,2,2,2,3], key = 2
Output: 2
Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key.
For target = 3, there is only one occurrence at index 4 which follows an occurrence of key.
target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.

Constraints:

2 <= nums.length <= 1000
1 <= nums[i] <= 1000
The test cases will be generated such that the answer is unique.

Solution: Hashtable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int mostFrequent(vector<int>& nums, int key) {

const int n = nums.size();

unordered_map<int, int> m;

int count = 0;

int ans = 0;

for (int i = 1; i < n; ++i) {

if (nums[i - 1] == key && ++m[nums[i]] > count) {

count = m[nums[i]];

ans = nums[i];

}

return ans;

}

};

花花酱 LeetCode 2197. Replace Non-Coprime Numbers in Array

By zxi on March 8, 2022

You are given an array of integers nums. Perform the following steps:

Find any two adjacent numbers in nums that are non-coprime.
If no such numbers are found, stop the process.
Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 10⁸.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation: 
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
The test cases are generated such that the values in the final array are less than or equal to 10⁸.

Solution: Stack

“””It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.”””

So that we can do it in one pass from left to right using a stack/vector.

Push the current number onto stack, and merge top two if they are not co-prime.

Time complexity: O(nlogm)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> replaceNonCoprimes(vector<int>& nums) {

vector<int> ans;

for (int x : nums) {

ans.push_back(x);

while (ans.size() > 1) {

const int n1 = ans[ans.size() - 1];

const int n2 = ans[ans.size() - 2];

const int d = gcd(n1, n2);

if (d == 1) break;

ans.pop_back();

ans.push_back(n1 / d * n2);

}

return ans;

}

};

花花酱 LeetCode 2196. Create Binary Tree From Descriptions

By zxi on March 8, 2022

You are given a 2D integer array descriptions where descriptions[i] = [parent_i, child_i, isLeft_i] indicates that parent_i is the parent of child_i in a binary tree of unique values. Furthermore,

If isLeft_i == 1, then child_i is the left child of parent_i.
If isLeft_i == 0, then child_i is the right child of parent_i.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Example 1:

Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.

Example 2:

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.

Constraints:

1 <= descriptions.length <= 10⁴
descriptions[i].length == 3
1 <= parent_i, child_i <= 10⁵
0 <= isLeft_i <= 1
The binary tree described by descriptions is valid.

Solution: Hashtable + Recursion

Use one hashtable to track the children of each node.
Use another hashtable to track the parent of each node.
Find the root who doesn’t have parent.
Build the tree recursively from root.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {

unordered_set<int> hasParent;

unordered_map<int, pair<int, int>> children;

for (const auto& d : descriptions) {

hasParent.insert(d[1]);

(d[2] ? children[d[0]].first : children[d[0]].second) = d[1];

}

int root = -1;

for (const auto& d : descriptions)

if (!hasParent.count(d[0])) root = d[0];

function<TreeNode*(int)> build = [&](int cur) -> TreeNode* {

if (!cur) return nullptr;

return new TreeNode(cur,

build(children[cur].first),

build(children[cur].second));

};

return build(root);

}

};

Huahua's Tech Road

花花酱 LeetCode 2206. Divide Array Into Equal Pairs

Solution: Hashtable

C++

花花酱 LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph

Solution: DFS

C++

花花酱 LeetCode 2190. Most Frequent Number Following Key In an Array

Solution: Hashtable

C++

花花酱 LeetCode 2197. Replace Non-Coprime Numbers in Array

Solution: Stack

C++

花花酱 LeetCode 2196. Create Binary Tree From Descriptions

Solution: Hashtable + Recursion

C++