Posts published in “Graph”

花花酱 LeetCode 1591. Strange Printer II

By zxi on September 20, 2020

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

class Solution {

public:

bool isPrintable(vector<vector<int>>& targetGrid) {

constexpr int kMaxC = 60;

const int m = targetGrid.size();

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

vector<unordered_set<int>> deps(kMaxC + 1);

for (int c = 1; c <= kMaxC; ++c) {

int l = n, r = -1, t = m, b = -1;

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

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

if (targetGrid[i][j] == c)

l = min(l, j), r = max(r, j), t = min(t, i), b = max(b, i);

if (l == -1) continue;

for (int i = t; i <= b; ++i)

for (int j = l; j <= r; ++j)

if (targetGrid[i][j] != c)

deps[c].insert(targetGrid[i][j]);

}

vector<int> seen(kMaxC + 1);

function<bool(int)> hasCycle = [&](int c) {

if (seen[c] == 1) return true;

if (seen[c] == 2) return false;

seen[c] = 1;

for (int t : deps[c])

if (hasCycle(t)) return true;

seen[c] = 2;

return false;

};

for (int c = 1; c <= kMaxC; ++c)

if (hasCycle(c)) return false;

return true;

}

};

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

By zxi on September 13, 2020

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

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
-10⁶ <= x_i, y_i <= 10⁶
All pairs (x_i, y_i) 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++

struct Edge {

int cost;

int x;

int y;

bool operator<(const Edge& e) const { return cost < e.cost; }

};

class Solution {

public:

int minCostConnectPoints(vector<vector<int>>& points) {

const int n = points.size();

vector<Edge> edges(n * (n - 1) / 2); // {cost, i, j}

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

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

edges[idx++] = {abs(points[i][0] - points[j][0]) +

abs(points[i][1] - points[j][1]), i, j};

std::sort(begin(edges), end(edges));

vector<int> p(n);

std::iota(begin(p), end(p), 0);

vector<int> rank(n, 0);

int ans = 0;

int count = 0;

for (const auto& e : edges) {

int rx = find(p, e.x);

int ry = find(p, e.y);

if (rx == ry) continue;

ans += e.cost;

if (rank[rx] < rank[ry]) swap(rx, ry);

p[rx] = ry;

rank[ry] += rank[rx] == rank[ry];

if (++count == n - 1) break;

}

return ans;

}

private:

int find(vector<int>& p, int x) const {

while (p[x] != x) {

int tp = p[x];

p[x] = p[p[x]];

x = tp;

}

return x;

}

};

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

class Solution {

public:

int minCostConnectPoints(vector<vector<int>>& points) {

const int n = points.size();

auto dist = [](const vector<int>& pi, const vector<int>& pj) {

return abs(pi[0] - pj[0]) + abs(pi[1] - pj[1]);

};

vector<int> ds(n, INT_MAX);

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

ds[i] = dist(points[0], points[i]);

int ans = 0;

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

auto it = min_element(begin(ds), end(ds));

const int v = distance(begin(ds), it);

ans += ds[v];

ds[v] = INT_MAX; // done

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

if (ds[i] == INT_MAX) continue;

ds[i] = min(ds[i], dist(points[i], points[v]));

}

return ans;

}

};

花花酱 LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

By zxi on September 6, 2020

Alice and Bob have an undirected graph of n nodes and 3 types of edges:

Type 1: Can be traversed by Alice only.
Type 2: Can be traversed by Bob only.
Type 3: Can by traversed by both Alice and Bob.

Given an array edges where edges[i] = [type_i, u_i, v_i] represents a bidirectional edge of type type_i between nodes u_i and v_i, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if it’s impossible for the graph to be fully traversed by Alice and Bob.

Example 1:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Example 2:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Example 3:

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

Constraints:

1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
All tuples (type_i, u_i, v_i) are distinct.

Solution: Greedy + Spanning Tree / Union Find

Use type 3 (both) edges first.

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

C++

class DSU {

public:

DSU(int n): p_(n + 1), e_(0) {

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

}

int find(int x) {

if (p_[x] == x) return x;

return p_[x] = find(p_[x]);

}

int merge(int x, int y) {

int rx = find(x);

int ry = find(y);

if (rx == ry) return 1;

p_[rx] = ry;

++e_;

return 0;

}

int edges() const { return e_; }

private:

vector<int> p_;

int e_;

};

class Solution {

public:

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

int ans = 0;

DSU A(n), B(n);

for (const auto& e: edges) {

if (e[0] != 3) continue;

ans += A.merge(e[1], e[2]);

B.merge(e[1], e[2]);

}

for (const auto& e: edges) {

if (e[0] == 3) continue;

DSU& d = e[0] == 1 ? A : B;

ans += d.merge(e[1], e[2]);

}

return (A.edges() == n - 1 && B.edges() == n - 1) ? ans : -1;

}

};

python3

class DSU:

def __init__(self, n: int):

self.p = list(range(n))

self.e = 0

def find(self, x: int) -> int:

if x != self.p[x]: self.p[x] = self.find(self.p[x])

return self.p[x]

def merge(self, x: int, y: int) -> int:

rx, ry = self.find(x), self.find(y)

if rx == ry: return 1

self.p[rx] = ry

self.e += 1

return 0

class Solution:

def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:

A, B = DSU(n + 1), DSU(n + 1)

ans = 0

for t, x, y in edges:

if t != 3: continue

ans += A.merge(x, y)

B.merge(x, y)

for t, x, y in edges:

if t == 3: continue

d = A if t == 1 else B

ans += d.merge(x, y)

return ans if A.e == B.e == n - 1 else -1

花花酱 LeetCode 1568. Minimum Number of Days to Disconnect Island

By zxi on August 30, 2020

Given a 2D grid consisting of 1s (land) and 0s (water). An island is a maximal 4-directionally (horizontal or vertical) connected group of 1s.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we are allowed to change any single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

Example 1:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.

Example 2:

Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Example 3:

Input: grid = [[1,0,1,0]]
Output: 0

Example 4:

Input: grid = [[1,1,0,1,1],
               [1,1,1,1,1],
               [1,1,0,1,1],
               [1,1,0,1,1]]
Output: 1

Example 5:

Input: grid = [[1,1,0,1,1],
               [1,1,1,1,1],
               [1,1,0,1,1],
               [1,1,1,1,1]]
Output: 2

Constraints:

1 <= grid.length, grid[i].length <= 30
grid[i][j] is 0 or 1.

Solution: Brute Force

We need at most two days to disconnect an island.
1. check if we have more than one islands. (0 days)
2. For each 1 cell, change it to 0 and check how many islands do we have. (1 days)
3. Otherwise, 2 days

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

C++

class Solution {

public:

int minDays(vector<vector<int>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

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

vector<int> seen(n * m);

function<void(int, int)> dfs = [&](int x, int y) {

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

if (grid[y][x] == 0) return;

if (seen[y * m + x]++) return;

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

dfs(x + dirs[i], y + dirs[i + 1]);

};

function<bool()> disconnected = [&]() {

int count = 0;

fill(begin(seen), end(seen), 0);

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

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

if (grid[y][x] && !seen[y * m + x]) {

dfs(x, y);

if (++count > 1) return true;

}

return false;

};

if (disconnected()) return 0;

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

for (int x = 0; x < m; ++x) {

if (!grid[y][x]) continue;

grid[y][x] = 0;

if (disconnected()) return 1;

grid[y][x] = 1;

}

return 2;

}

};

花花酱 LeetCode 1559. Detect Cycles in 2D Grid

By zxi on August 23, 2020

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it – in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid consists only of lowercase English letters.

Solution: DFS

Finding a cycle in an undirected graph => visiting a node that has already been visited and it’s not the parent node of the current node.
b b
b b
null -> (0, 0) -> (0, 1) -> (1, 1) -> (1, 0) -> (0, 0)
The second time we visit (0, 0) which has already been visited before and it’s not the parent of the current node (1, 0) ( (1, 0)’s parent is (1, 1) ) which means we found a cycle.

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

C++

class Solution {

public:

bool containsCycle(vector<vector<char>>& grid) {

const int m = grid.size();

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

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

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

function<bool(int, int, int, int)> dfs = [&](int i, int j, int pi, int pj) {

++seen[i][j];

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

int ni = i + dirs[d];

int nj = j + dirs[d + 1];

if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;

if (grid[ni][nj] != grid[i][j]) continue;

if (!seen[ni][nj]) {

if (dfs(ni, nj, i, j)) return true;

} else if (ni != pi || nj != pj) {

return true;

}

return false;

};

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

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

if (!seen[i][j]++ && dfs(i, j, -1, -1))

return true;

return false;

}

};