Press "Enter" to skip to content

Posts published in “Graph”

花花酱 LeetCode 1631. Path With Minimum Effort

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 updownleft, 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] <= 106

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++

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++

Solution 3: Dijkstra

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

C++

花花酱 LeetCode 1627. Graph Connectivity With Threshold

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] = [ai, bi] if cities ai and bi 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 ith query, there is a path between ai and bi, 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 <= 104
  • 0 <= threshold <= n
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 1 <= ai, bi <= cities
  • ai != bi

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++

Python3

花花酱 LeetCode 1615. Maximal Network Rank

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

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 <= ai, bi <= n-1
  • ai != bi
  • 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++

花花酱 LeetCode 1591. Strange Printer II

There is a strange printer with the following two special requirements:

  • On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
  • Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

Constraints:

  • m == targetGrid.length
  • n == targetGrid[i].length
  • 1 <= m, n <= 60
  • 1 <= targetGrid[row][col] <= 60

Solution: Dependency graph

For each color C find the maximum rectangle to cover it. Any other color C’ in this rectangle is a dependency of C, e.g. C’ must be print first in order to print C.

Then this problem reduced to check if there is any cycle in the dependency graph.

e.g.
1 2 1
2 1 2
1 2 1
The maximum rectangle for 1 and 2 are both [0, 0] ~ [2, 2]. 1 depends on 2, and 2 depends on 1. This is a circular reference and no way to print.

Time complexity: O(C*M*N)
Space complexity: O(C*C)

C++

花花酱 LeetCode 1584. Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Example 3:

Input: points = [[0,0],[1,1],[1,0],[-1,1]]
Output: 4

Example 4:

Input: points = [[-1000000,-1000000],[1000000,1000000]]
Output: 4000000

Example 5:

Input: points = [[0,0]]
Output: 0

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.

Solution: Minimum Spanning Tree

Kruskal’s algorithm
Time complexity: O(n^2logn)
Space complexity: O(n^2)
using vector of vector, array, pair of pair, or tuple might lead to TLE…

C++

Prim’s Algorithm
ds[i] := min distance from i to ANY nodes in the tree.

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

C++