Posts tagged as “graph”

花花酱 LeetCode 1632. Rank Transform of a Matrix

By zxi on October 28, 2020

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

The rank is an integer starting from 1.
If two elements p and q are in the same row or column, then:
- If p < q then rank(p) < rank(q)
- If p == q then rank(p) == rank(q)
- If p > q then rank(p) > rank(q)
The rank should be as small as possible.

It is guaranteed that answer is unique under the given rules.

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2:

Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]

Example 3:

Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

Example 4:

Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

Solution: Union Find

Group cells by their values, process groups (cells that have the same value) in ascending order (smaller number has smaller rank).

For cells that are in the same row and same cols union them using union find, they should have the same rank which equals to max(max_rank_x[cols], max_rank_y[rows]) + 1.

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

C++

// Author: Huahua

class DSU {

public:

DSU(int n): p_(n, -1) {}

int find(int x) {

return p_[x] == -1 ? x : p_[x] = find(p_[x]);

}

void merge(int x, int y) {

x = find(x), y = find(y);

if (x != y) p_[x] = y;

}

private:

vector<int> p_;

};

class Solution {

public:

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

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

map<int, vector<pair<int, int>>> mp; // val -> {positions}

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

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

mp[matrix[y][x]].emplace_back(x, y);

vector<int> rx(n), ry(m);

for (const auto& [val, ps]: mp) {

DSU dsu(n + m);

vector<vector<pair<int, int>>> cc(n + m); // val -> {positions}

for (const auto& [x, y]: ps)

dsu.merge(x, y + n);

for (const auto& [x, y]: ps)

cc[dsu.find(x)].emplace_back(x, y);

for (const auto& ps: cc) {

int rank = 1;

for (const auto& [x, y]: ps)

rank = max(rank, max(rx[x], ry[y]) + 1);

for (const auto& [x, y]: ps)

rx[x] = ry[y] = ans[y][x] = rank;

}

return ans;

}

};

花花酱 LeetCode 1631. Path With Minimum Effort

By zxi on October 24, 2020

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute differencein heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10⁶

Solution: “Lazy BFS / DP”

dp[y][x] = min(max(dp[ty][tx], abs(h[ty][tx] – h[y][x]))) (x, y) and (tx, ty) are neighbors
repeat this process for at most rows * cols times.
if dp does not change after one round which means we found the optimal solution and can break earlier.

Time complexity: O(n^2*m^2))
Space complexity: O(nm)

C++

// Author: Huahua, 824 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const int r = heights.size();

const int c = heights[0].size();

int dp[100][100];

memset(dp, 0x7f, sizeof(dp));

dp[0][0] = 0;

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

for (int k = 0; k < r * c; ++k) {

bool stable = true;

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

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

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

int tx = x + dirs[d];

int ty = y + dirs[d + 1];

if (tx < 0 || tx == c || ty < 0 || ty == r) continue;

int t = max(dp[ty][tx], abs(heights[ty][tx] - heights[y][x]));

if (t < dp[y][x]) {

stable = false;

dp[y][x] = t;

}

if (stable) break;

}

return dp[r - 1][c - 1];

}

};

Solution 2: Binary Search + BFS

Use binary search to guess a cost and then check whether there is path that is under the cost.

Time complexity: O(mn*log(max(h) – min(h)))
Space complexity: O(mn)

C++

// Author: Huahua, 620 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const int rows = heights.size();

const int cols = heights[0].size();

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

auto bfs = [&](int cost) -> bool {

queue<pair<int, int>> q;

vector<int> seen(cols * rows);

q.emplace(0, 0);

seen[0] = 1;

while (!q.empty()) {

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

if (cx == cols - 1 && cy == rows - 1) return true;

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

int x = cx + dirs[i];

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

if (x < 0 || x == cols || y < 0 || y == rows) continue;

if (abs(heights[cy][cx] - heights[y][x]) > cost) continue;

if (seen[y * cols + x]++) continue;

q.emplace(x, y);

}

return false;

};

int l = 0, r = 1e6 + 1;

while (l < r) {

const int m = l + (r - l) / 2;

if (bfs(m)) {

r = m;

} else {

l = m + 1;

}

return l;

}

};

Solution 3: Dijkstra

Time complexity: O(mnlog(mn))
Space complexity: O(mn)

C++

// Author: Huahua, 216 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

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

const int rows = heights.size();

const int cols = heights[0].size();

using Node = pair<int, int>;

priority_queue<Node, vector<Node>, greater<Node>> q;

vector<int> dist(rows * cols, INT_MAX / 2);

q.emplace(0, 0);

dist[0] = 0;

while (!q.empty()) {

auto [t, u] = q.top(); q.pop();

if (u == rows * cols - 1) return t;

if (t > dist[u]) continue;

const int ux = u % cols;

const int uy = u / cols;

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

const int x = ux + dirs[i];

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

if (x < 0 || x == cols || y < 0 || y == rows) continue;

const int v = y * cols + x;

const int c = abs(heights[uy][ux] - heights[y][x]);

if (max(t, c) >= dist[v]) continue;

q.emplace(dist[v] = max(t, c), v);

}

return -1;

}

};

花花酱 LeetCode 1627. Graph Connectivity With Threshold

By zxi on October 18, 2020

We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:

x % z == 0,
y % z == 0, and
z > threshold.

Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [a_i, b_i] if cities a_i and b_i are connected (i.e. there is some path between them).

Return an array answer, where answer.length == queries.length and answer[i] is true if for the i^th query, there is a path between a_i and b_i, or answer[i] is false if there is no path.

Example 1:

Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
Output: [false,false,true]
Explanation: The divisors for each number:
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the
only ones directly connected. The result of each query:
[1,4]   1 is not connected to 4
[2,5]   2 is not connected to 5
[3,6]   3 is connected to 6 through path 3--6

Example 2:

Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
Output: [true,true,true,true,true]
Explanation: The divisors for each number are the same as the previous example. However, since the threshold is 0,
all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.

Example 3:

Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
Output: [false,false,false,false,false]
Explanation: Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected.
Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x].

Constraints:

2 <= n <= 10⁴
0 <= threshold <= n
1 <= queries.length <= 10⁵
queries[i].length == 2
1 <= a_i, b_i <= cities
a_i != b_i

Solution: Union Find

For x, merge 2x, 3x, 4x, ..,
If a number is already “merged”, skip it.

Time complexity: O(nlogn? + queries)?
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {

if (threshold == 0) return vector<bool>(queries.size(), true);

vector<int> ds(n + 1);

iota(begin(ds), end(ds), 0);

function<int(int)> find = [&](int x) {

return ds[x] == x ? x : ds[x] = find(ds[x]);

};

for (int x = threshold + 1; x <= n; ++x)

if (ds[x] == x)

for (int y = 2 * x; y <= n; y += x)

ds[max(find(x), find(y))] = min(find(x), find(y));

vector<bool> ans;

for (const vector<int>& q : queries)

ans.push_back(find(q[0]) == find(q[1]));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def areConnected(self, n: int, threshold: int,

queries: List[List[int]]) -> List[bool]:

if threshold == 0: return [True] * len(queries)

ds = list(range(n + 1))

def find(x: int) -> int:

if x != ds[x]: ds[x] = find(ds[x])

return ds[x]

for x in range(threshold + 1, n + 1):

if ds[x] == x:

for y in range(2 * x, n + 1, x):

ds[max(find(x), find(y))] = min(find(x), find(y))

return [find(x) == find(y) for x, y in queries]

花花酱 LeetCode 1617. Count Subtrees With Max Distance Between Cities

By zxi on October 11, 2020

There are n cities numbered from 1 to n. You are given an array edges of size n-1, where edges[i] = [u_i, v_i] represents a bidirectional edge between cities u_i and v_i. There exists a unique path between each pair of cities. In other words, the cities form a tree.

A subtree is a subset of cities where every city is reachable from every other city in the subset, where the path between each pair passes through only the cities from the subset. Two subtrees are different if there is a city in one subtree that is not present in the other.

For each d from 1 to n-1, find the number of subtrees in which the maximum distance between any two cities in the subtree is equal to d.

Return an array of size n-1 where the d^thelement (1-indexed) is the number of subtrees in which the maximum distance between any two cities is equal to d.

Notice that the distance between the two cities is the number of edges in the path between them.

Example 1:

Input: n = 4, edges = [[1,2],[2,3],[2,4]]
Output: [3,4,0]
Explanation:
The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.
The subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.
No subtree has two nodes where the max distance between them is 3.

Example 2:

Input: n = 2, edges = [[1,2]]
Output: [1]

Example 3:

Input: n = 3, edges = [[1,2],[2,3]]
Output: [2,1]

Constraints:

2 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= u_i, v_i <= n
All pairs (u_i, v_i) are distinct.

Solution1: Brute Force + Diameter of tree

Try all subtrees and find the diameter of that subtree (longest distance between any node)

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges, int last = -1) {

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

for (const auto& e : edges)

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

vector<int> seen(n, -1), seen2;

queue<int> q;

auto bfs = [&](int start, vector<int>& seen) -> pair<int, int> {

q.push(start);

seen[start] = 1;

int count = 0, dist = -1;

while (!q.empty()) {

int s = q.size();

while (s--) {

last = q.front(); q.pop();

++count;

for (int v : g[last])

if (seen[v] != -1 && !seen[v]++) q.push(v);

}

++dist;

}

return {dist, count};

};

vector<int> ans(n - 1);

for (int s = 0; s < 1 << n; ++s) {

if (__builtin_popcount(s) <= 1) continue;

fill(begin(seen), end(seen), -1);

for (int i = 0; i < n; ++i) if (s & (1 << i)) seen[i] = 0;

seen2 = seen;

const int start = 31 - __builtin_clz(s & (s - 1));

if (bfs(start, seen).second != __builtin_popcount(s)) continue;

++ans[bfs(last, seen2).first - 1];

}

return ans;

}

};

Solution 2: DP on Trees

dp[i][k][d] := # of subtrees rooted at i with tree diameter of d and the distance from i to the farthest node is k.

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

C++

// Author: Huahua, 4ms, 8.8MB

class Solution {

public:

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

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

for (const auto& e : edges) {

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

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

}

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

vector<int> sizes(n);

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

if (!dp[u].empty()) return;

dp[u] = vector<vector<int>>(n, vector<int>(n));

dp[u][0][0] = 1;

sizes[u] = 1;

for (int v : g[u]) {

if (v == p) continue;

dfs(v, u);

vector<vector<int>> dpu(dp[u]);

for (int d1 = 0; d1 < sizes[u]; ++d1)

for (int k1 = 0; k1 <= d1; ++k1) {

if (!dp[u][k1][d1]) continue;

for (int d2 = 0; d2 < sizes[v]; ++d2)

for (int k2 = 0; k2 <= d2; ++k2) {

const int d = max({d1, d2, k1 + k2 + 1});

const int k = max(k1, k2 + 1);

dpu[k][d] += dp[u][k1][d1] * dp[v][k2][d2];

}

swap(dpu, dp[u]);

sizes[u] += sizes[v];

}

};

vector<int> ans(n - 1);

dfs(0, -1);

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

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

for (int d = 1; d < n; ++d)

ans[d - 1] += dp[i][k][d];

return ans;

}

};

花花酱 LeetCode 1615. Maximal Network Rank

By zxi on October 10, 2020

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.

The network rankof two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints:

2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= a_i, b_i <= n-1
a_i != b_i
Each pair of cities has at most one road connecting them.

Solution: Counting degrees and all pairs

Counting degrees for each node, if a and b are not connected, ans = degrees(a) + degrees(b), otherwise ans -= 1

Time complexity: O(E + V^2)
Space complexity: O(E)

C++

// Author: Huahua

class Solution {

public:

int maximalNetworkRank(int n, vector<vector<int>>& roads) {

vector<int> degrees(n);

unordered_set<int> connected;

for (const auto& road : roads) {

++degrees[road[0]];

++degrees[road[1]];

connected.insert((road[0] << 16) | road[1]);

connected.insert((road[1] << 16) | road[0]);

}

int ans = 0;

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

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

ans = max(ans, degrees[i] + degrees[j]

- (connected.count((i << 16) | j) ? 1 : 0));

return ans;

}

};