Posts published in “Graph”

花花酱 LeetCode 1162. As Far from Land as Possible

By zxi on August 17, 2019

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1)is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

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

Solution: BFS

Put all land cells into a queue as source nodes and BFS for water cells, the last expanded one will be the farthest.

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

C++

// Author: Huahua, 48 ms, 13.4 MB

class Solution {

public:

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

const int n = grid.size();

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

int ans = -1;

queue<int> q; // y*100 + x

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

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

if (grid[i][j] == 1) q.push(i * 100 + j);

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

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int x = p % 100;

int y = p / 100;

if (grid[y][x] == 2)

ans = max(ans, steps);

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

int tx = x + dirs[i];

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

if (tx < 0 || tx >= m || ty < 0 || ty >= n || grid[ty][tx] != 0) continue;

grid[ty][tx] = 2;

q.push(ty * 100 + tx);

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 1129. Shortest Path with Alternating Colors

By zxi on July 20, 2019

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

Solution: BFS

Time complexity: O(|V| + |E|)
Space complexity: O(|V| + |E|)

C++

class Solution {

public:

vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {

vector<unordered_set<int>> edges_r(n);

vector<unordered_set<int>> edges_b(n);

for (const auto& e : red_edges)

edges_r[e[0]].insert(e[1]);

for (const auto& e : blue_edges)

edges_b[e[0]].insert(e[1]);

unordered_set<int> seen_r;

unordered_set<int> seen_b;

vector<int> ans(n, -1);

queue<pair<int, int>> q; // (node, color)

q.push({0, 0}); // red

q.push({0, 1}); // blue

seen_r.insert(0);

seen_b.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int p = q.front().first;

int is_red = q.front().second;

q.pop();

ans[p] = ans[p] >= 0 ? min(ans[p], steps) : steps;

const auto& edges = is_red ? edges_r : edges_b;

auto& seen = is_red ? seen_r : seen_b;

for (int nxt : edges[p]) {

if (seen.count(nxt)) continue;

seen.insert(nxt);

q.push({nxt, 1 - is_red});

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 1042. Flower Planting With No Adjacent

By zxi on May 14, 2019

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.

Solution: Graph coloring, choose any available color

Time complexity: O(|V|+|E|)
Space complexity: O(|V|+|E|)

C++

class Solution {

public:

vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {

vector<int> ans(N, 0);

vector<vector<int>> G(N);

for (const auto& p : paths) {

G[p[0] - 1].push_back(p[1] - 1);

G[p[1] - 1].push_back(p[0] - 1);

}

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

int mask = 0;

for (const auto& j : G[i])

mask |= (1 << ans[j]);

for (int c = 1; c <= 4 && ans[i] == 0; ++c)

if (!(mask & (1 << c))) ans[i] = c;

}

return ans;

}

};

花花酱 LeetCode 851. Loud and Rich

By zxi on May 4, 2019

In a group of N people (labelled 0, 1, 2, ..., N-1), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label x, simply “person x“.

We’ll say that richer[i] = [x, y] if person x definitely has more money than person y. Note that richer may only be a subset of valid observations.

Also, we’ll say quiet[x] = q if person x has quietness q.

Now, return answer, where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]), among all people who definitely have equal to or more money than person x.

Example 1:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

answer[7] = 7.
Among all people that definitely have equal to or more money than person 7
(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])
is person 7.

The other answers can be filled out with similar reasoning.

Note:

1 <= quiet.length = N <= 500
0 <= quiet[i] < N, all quiet[i] are different.
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]‘s are all different.
The observations in richer are all logically consistent.

Solution: DFS + Memoization

For person i , remember the quietest person who is richer than person i.

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

C++

// Author: Huahua, running time: 108 ms, 31.6 MB

class Solution {

public:

vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {

const int n = quiet.size();

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

for (const auto& r : richer)

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

vector<int> ans(n, -1);

function<void(int)> dfs = [&](int i) {

if (ans[i] != -1) return;

ans[i] = i;

for (int j : g[i]) {

dfs(j);

if (quiet[ans[j]] < quiet[ans[i]])

ans[i] = ans[j];

}

};

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

return ans;

}

};

花花酱 LeetCode 997. Find the Town Judge

By zxi on February 23, 2019

In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

Example 1:

Input: N = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: N = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Example 4:

Input: N = 3, trust = [[1,2],[2,3]]
Output: -1

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Note:

1 <= N <= 1000
trust.length <= 10000
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

Solution: Degree

node with degree (in_degree – out_degree) N – 1 is the judge.

Time complexity: O(N+T)
Space complexity: O(N)

C++

class Solution {

public:

int findJudge(int N, vector<vector<int>>& trusts) {

vector<int> degrees(N + 1);

for (const auto& trust : trusts) {

--degrees[trust[0]];

++degrees[trust[1]];

}

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

if (degrees[i] == N - 1) return i;

return -1;

}

};