Huahua’s Tech Road

花花酱 LeetCode 1253. Reconstruct a 2-Row Binary Matrix

By zxi on November 9, 2019

Given the following details of a matrix with n columns and 2 rows :

The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
The sum of elements of the 0-th(upper) row is given as upper.
The sum of elements of the 1-st(lower) row is given as lower.
The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

Solution: Greedy?

Two passes:
first pass, only process sum = 2, upper = 1, lower = 1
second pass, only process sum = 1, whoever has more leftover, assign 1 to that row.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {

const int n = colsum.size();

vector<vector<int>> a(2, vector<int>(n));

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

if (colsum[i] == 2) {

a[0][i] = a[1][i] = 1;

--upper;

--lower;

}

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

if (colsum[i] == 1)

if (upper > lower) {

a[0][i] = 1;

--upper;

} else {

a[1][i] = 1;

--lower;

}

if (upper != 0 || lower != 0) return {};

return a;

}

};

花花酱 LeetCode 1254. Number of Closed Islands

By zxi on November 9, 2019

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

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

Constraints:

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

Solution: DFS/Backtracking

For each connected component, if it can reach the boundary then it’s not a closed island.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = grid.size();

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

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

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

if (grid[y][x]++) return 1;

return dfs(x + 1, y) & dfs(x - 1, y) & dfs(x, y + 1) & dfs(x, y - 1);

};

int ans = 0;

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

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

if (!grid[i][j]) ans += dfs(j, i);

return ans;

}

};

花花酱 LeetCode 1252. Cells with Odd Values in a Matrix

By zxi on November 9, 2019

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

Constraints:

1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m

Solution 1: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int oddCells(int n, int m, vector<vector<int>>& indices) {

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

for (const auto& idx : indices) {

for (int x = 0; x < m; ++x) ++a[idx[0]][x];

for (int y = 0; y < n; ++y) ++a[y][idx[1]];

}

int ans = 0;

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

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

ans += a[i][j] & 1;

return ans;

}

};

Solution 2: Counting

For each row and column, compute how many times it will be increased (odd or even).
For each a[i][j], check how many times the i-th row and j-th column were increased, if the sum is odd then a[i][j] will odd.
Time complexity: O(n*m + k)
Space complexity: O(n+m)

C++

// Author: Huahua

class Solution {

public:

int oddCells(int n, int m, vector<vector<int>>& indices) {

vector<int> cols(m);

vector<int> rows(n);

for (const auto& idx : indices) {

rows[idx[0]] ^= 1;

cols[idx[1]] ^= 1;

}

int ans = 0;

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

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

ans += rows[i] ^ cols[j];

return ans;

}

};

花花酱 1249. Minimum Remove to Make Valid Parentheses

By zxi on November 9, 2019

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.

Solution: Couting

Count how many “(” are open and how many “)” left.

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

C++

// Author: Huahua

class Solution {

public:

string minRemoveToMakeValid(string s) {

int close = count(begin(s), end(s), ')');

int open = 0;

string ans;

for (char c : s) {

if (c == '(') {

if (open == close) continue;

++open;

} else if (c == ')') {

--close;

if (open == 0) continue;

--open;

}

ans += c;

}

return ans;

}

};

花花酱 LeetCode 1250. Check If It Is a Good Array

By zxi on November 8, 2019

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Solution: Math

Bézout’s lemma: b[1] * A[1] + b[2] * A[2] + …. + b[n] * A[n] = 1 <==> gcd(A[1], A[2], …, A[n]) = 1 <=> at least two numbers are co-prime

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

C++

// Author: Huahua

class Solution {

public:

bool isGoodArray(vector<int>& nums) {

int g = nums[0];

for (int x : nums)

g = gcd(g, x);

return g == 1;

}

};

Huahua's Tech Road

花花酱 LeetCode 1253. Reconstruct a 2-Row Binary Matrix

Solution: Greedy?

C++

花花酱 LeetCode 1254. Number of Closed Islands

Solution: DFS/Backtracking

C++

花花酱 LeetCode 1252. Cells with Odd Values in a Matrix

Solution 1: Simulation

C++

Solution 2: Counting

C++

花花酱 1249. Minimum Remove to Make Valid Parentheses

Solution: Couting

C++

花花酱 LeetCode 1250. Check If It Is a Good Array

Solution: Math

C++