Huahua’s Tech Road

花花酱 LeetCode 1582. Special Positions in a Binary Matrix

By zxi on September 12, 2020

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],
              [0,0,1],
              [1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],
              [0,1,0],
              [0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.

Example 3:

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

Example 4:

Input: mat = [[0,0,0,0,0],
              [1,0,0,0,0],
              [0,1,0,0,0],
              [0,0,1,0,0],
              [0,0,0,1,1]]
Output: 3

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 1.

Solution: Sum for each row and column

Brute force:
Time complexity: O(R*C*(R+C))
Space complexity: O(1)

We can pre-compute the sums for each row and each column, ans = sum(mat[r][c] == 1 and rsum[r] == 1 and csum[c] == 1)

Time complexity: O(R*C)
Space complexity: O(R+C)

C++

class Solution {

public:

int numSpecial(vector<vector<int>>& mat) {

const int rows = mat.size();

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

vector<int> rs(rows);

vector<int> cs(cols);

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

for (int c = 0; c < cols; ++c) {

rs[r] += mat[r][c];

cs[c] += mat[r][c];

}

int ans = 0;

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

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

ans += mat[r][c] && rs[r] == 1 && cs[c] == 1;

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 1578. Minimum Deletion Cost to Avoid Repeating Letters

By zxi on September 5, 2020

Given a string s and an array of integers cost where cost[i] is the cost of deleting the character i in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).

Example 2:

Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.

Example 3:

Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").

Constraints:

s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s contains only lowercase English letters.

Solution: Group by group

For a group of same letters, delete all expect the one with the highest cost.

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

C++

class Solution {

public:

int minCost(string s, vector<int>& cost) {

int t = cost[0];

int m = cost[0];

int ans = 0;

for (int i = 1; i < s.length(); ++i) {

if (s[i] != s[i - 1]) {

ans += t - m;

t = m = 0;

}

t += cost[i];

m = max(m, cost[i]);

}

return ans + (t - m);

}

};

python3

class Solution:

def minCost(self, s: str, cost: List[int]) -> int:

s = '*' + s + '*'

cost = [0] + cost + [0]

ans = t = m = 0

for i in range(1, len(s)):

if s[i] != s[i - 1]:

ans += t - m

t = m = 0

t += cost[i]

m = max(m, cost[i])

return ans

花花酱 LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

By zxi on September 5, 2020

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]² == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]² == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8).

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].

Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

Example 4:

Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.

Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5

Solution: Hashtable

For each number y in the second array, count its frequency.

For each number x in the first, if x * x % y == 0, let r = x * x / y
if r == y: ans += f[y] * f[y-1]
else ans += f[y] * f[r]

Final ans /= 2

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

C++

// Author: Huahua

class Solution {

public:

int numTriplets(vector<int>& nums1, vector<int>& nums2) {

return solve(nums1, nums2) + solve(nums2, nums1);

}

private:

int solve(vector<int>& nums1, vector<int>& nums2) {

int ans = 0;

unordered_map<int, int> f;

for (int y : nums2) ++f[y];

for (long x : nums1)

for (const auto& [y, c] : f) {

long r = x * x / y;

if (x * x % y || !f.count(r)) continue;

if (r == y) ans += c * (c - 1);

else ans += c * f[r];

}

return ans / 2;

}

};

花花酱 LeetCode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

By zxi on September 5, 2020

Given a string s containing only lower case English letters and the ‘?’ character, convert all the ‘?’ characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non ‘?’ characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for ‘?’.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:

Input: s = "??yw?ipkj?"
Output: "acywaipkja"

Constraints:

1 <= s.length <= 100
s contains only lower case English letters and ‘?’.

Solution: Greedy

For each ?, find the first one among ‘abc’ that is not same as left or right.

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

C++

class Solution {

public:

string modifyString(string s) {

const int n = s.length();

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

if (s[i] != '?') continue;

for (char c : "abc")

if ((i == 0 || s[i - 1] != c) && (i == n - 1 || s[i + 1] != c)) {

s[i] = c;

break;

}

return s;

}

};

Huahua's Tech Road

花花酱 LeetCode 1582. Special Positions in a Binary Matrix

Solution: Sum for each row and column

C++

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

Solution: Greedy + Spanning Tree / Union Find

C++

python3

花花酱 LeetCode 1578. Minimum Deletion Cost to Avoid Repeating Letters

Solution: Group by group

C++

python3

花花酱 LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Solution: Hashtable

C++

花花酱 LeetCode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

Solution: Greedy

C++