Huahua’s Tech Road

花花酱 LeetCode 1766. Tree of Coprimes

By zxi on February 20, 2021

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the i^th node’s value, and each edges[j] = [u_j, v_j] represents an edge between nodes u_j and v_j in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: [-1,0,-1,0,0,0,-1]

Constraints:

nums.length == n
1 <= nums[i] <= 50
1 <= n <= 10⁵
edges.length == n - 1
edges[j].length == 2
0 <= u_j, v_j < n
u_j != v_j

Solution: DFS + Stack

Pre-compute for coprimes for each number.

For each node, enumerate all it’s coprime numbers, find the deepest occurrence.

Time complexity: O(n * max(nums))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {

constexpr int kMax = 50;

const int n = nums.size();

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

for (const auto& e : edges) {

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

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

}

vector<vector<int>> coprime(kMax + 1);

for (int i = 1; i <= kMax; ++i)

for (int j = 1; j <= kMax; ++j)

if (gcd(i, j) == 1) coprime[i].push_back(j);

vector<int> ans(n, INT_MAX);

vector<vector<pair<int, int>>> p(kMax + 1);

function<void(int, int)> dfs = [&](int cur, int d) {

int max_d = -1;

int ancestor = -1;

for (int co : coprime[nums[cur]])

if (!p[co].empty() && p[co].back().first > max_d) {

max_d = p[co].back().first;

ancestor = p[co].back().second;

}

ans[cur] = ancestor;

p[nums[cur]].emplace_back(d, cur);

for (int nxt : g[cur])

if (ans[nxt] == INT_MAX) dfs(nxt, d + 1);

p[nums[cur]].pop_back();

};

dfs(0, 0);

return ans;

}

};

花花酱 LeetCode 1765. Map of Highest Peak

By zxi on February 20, 2021

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.
If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

The height of each cell must be non-negative.
If the cell is a water cell, its height must be 0.
Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)‘s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] is 0 or 1.
There is at least one water cell.

Solution: BFS

h[y][x] = min distance of (x, y) to any water cell.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {

const int m = isWater.size();

const int n = isWater[0].size();

vector<vector<int>> ans(m, vector<int>(n, INT_MIN));

queue<pair<int, int>> q;

for (int y = 0; y < m; ++y)

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

if (isWater[y][x]) {

q.emplace(x, y);

ans[y][x] = 0;

}

const vector<int> dirs{0, -1, 0, 1, 0};

while (!q.empty()) {

const auto [cx, cy] = q.front();

q.pop();

for (int i = 0; i < 4; ++i) {

const int x = cx + dirs[i];

const int y = cy + dirs[i + 1];

if (x < 0 || x >= n || y < 0 || y >= m) continue;

if (ans[y][x] != INT_MIN) continue;

ans[y][x] = ans[cy][cx] + 1;

q.emplace(x, y);

}

return ans;

}

};

花花酱 LeetCode 1764. Form Array by Concatenating Subarrays of Another Array

By zxi on February 20, 2021

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the i^th subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)^th subarray appears before the i^th subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true if you can do this task, and false otherwise.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0^th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1^st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.

Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].

Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).

Constraints:

groups.length == n
1 <= n <= 10³
1 <= groups[i].length, sum(groups[i].length) <= 10³
1 <= nums.length <= 10³
-10⁷ <= groups[i][j], nums[k] <= 10⁷

Solution: Brute Force

Time complexity: O(n^2?)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {

const int n = nums.size();

int s = 0;

for (const auto& g : groups) {

bool found = false;

for (int i = s; i <= n - g.size(); ++i)

if (equal(begin(g), end(g), begin(nums) + i)) {

s = i + g.size();

found = true;

break;

}

if (!found) return false;

}

return true;

}

};

花花酱 LeetCode 1763. Longest Nice Substring

By zxi on February 20, 2021

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3:

Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Example 4:

Input: s = "dDzeE"
Output: "dD"
Explanation: Both "dD" and "eE" are the longest nice substrings.
As there are multiple longest nice substrings, return "dD" since it occurs earlier.

Constraints:

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

Solution: Brute Force

Time complexity: O(n^3)
Space complexity: O(1)

C++

class Solution {

public:

string longestNiceSubstring(string_view s) {

const int n = s.length();

auto isNice = [](string_view s) {

vector<int> u(26), l(26);

for (int c : s)

if (isupper(c)) u[c - 'A'] = 1;

else l[c - 'a'] = 1;

return u == l;

};

string_view ans;

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

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

string_view ss = s.substr(i, j - i + 1);

if (isNice(ss) && ss.length() > ans.length())

ans = ss;

}

return string(ans);

}

};

Optimized 1:

Time complexity: O(n^2*26)
Space complexity: O(1)

C++

class Solution {

public:

string longestNiceSubstring(string_view s) {

const int n = s.length();

string_view ans;

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

vector<int> u(26), l(26);

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

const char c = s[j];

if (isupper(c)) u[c - 'A'] = 1;

else l[c - 'a'] = 1;

if (u == l && j - i + 1 > ans.length())

ans = s.substr(i, j - i + 1);

}

return string(ans);

}

};

花花酱 LeetCode 1761. Minimum Degree of a Connected Trio in a Graph

By zxi on February 13, 2021

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [u_i, v_i] indicates that there is an undirected edge between u_i and v_i.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

Constraints:

2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= u_i, v_i <= n
u_i!= v_i
There are no repeated edges.

Solution: Brute Force

Try all possible Trios.

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

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

vector<bitset<400>> g(n);

for (const auto& e : edges) {

g[e[0] - 1].set(e[1] - 1);

g[e[1] - 1].set(e[0] - 1);

}

size_t ans = INT_MAX;

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

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

if (g[i][j])

for (int k = j + 1; k < n; ++k)

if (g[i][k] && g[j][k])

ans = min(ans, g[i].count() + g[j].count() + g[k].count() - 6);

return ans == INT_MAX ? -1 : ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1766. Tree of Coprimes

Solution: DFS + Stack

C++

花花酱 LeetCode 1765. Map of Highest Peak

Solution: BFS

C++

花花酱 LeetCode 1764. Form Array by Concatenating Subarrays of Another Array

Solution: Brute Force

C++

花花酱 LeetCode 1763. Longest Nice Substring

Solution: Brute Force

C++

C++

花花酱 LeetCode 1761. Minimum Degree of a Connected Trio in a Graph

Solution: Brute Force

C++