Posts published in “Graph”

花花酱 LeetCode 1697. Checking Existence of Edge Length Limited Paths

By zxi on December 20, 2020

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [u_i, v_i, dis_i] denotes an edge between nodes u_i and v_i with distance dis_i. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [p_j, q_j, limit_j], your task is to determine for each queries[j] whether there is a path between p_j and q_jsuch that each edge on the path has a distance strictly less than limit_j .

Return a boolean array answer, where answer.length == queries.length and the j^th value of answer is true if there is a path for queries[j] is true, and false otherwise.

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Exaplanation: The above figure shows the given graph.

Constraints:

2 <= n <= 10⁵
1 <= edgeList.length, queries.length <= 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 <= u_i, v_i, p_j, q_j <= n - 1
u_i != v_i
p_j != q_j
1 <= dis_i, limit_j <= 10⁹
There may be multiple edges between two nodes.

Solution: Union Find

Since queries are offline, we can reorder them to optimize time complexity. Answer queries by their limits in ascending order while union edges by weights up to the limit. In this case, we just need to go through the entire edge list at most once.

Time complexity: O(QlogQ + ElogE)
Space complexity: O(Q + E)

C++

// Author: Huahua

class Solution {

public:

vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {

vector<int> parents(n);

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

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

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

};

const int m = Q.size();

for (int i = 0; i < m; ++i) Q[i].push_back(i);

// Sort edges by weight in ascending order.

sort(begin(E), end(E), [](const auto& a, const auto& b) { return a[2] < b[2]; });

// Sort queries by limit in ascending order

sort(begin(Q), end(Q), [](const auto& a, const auto& b) { return a[2] < b[2]; });

vector<bool> ans(m);

int i = 0;

for (const auto& q : Q) {

while (i < E.size() && E[i][2] < q[2])

parents[find(E[i++][0])] = find(E[i][1]);

ans[q[3]] = find(q[0]) == find(q[1]);

}

return ans;

}

};

花花酱 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 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;

}

};