Huahua’s Tech Road

花花酱 LeetCode 1896. Minimum Cost to Change the Final Value of Expression

By zxi on August 9, 2021

You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.

For example, "()1|1" and "(1)&()" are not valid while "1", "(((1))|(0))", and "1|(0&(1))" are valid expressions.

Return the minimum cost to change the final value of the expression.

For example, if expression = "1|1|(0&0)&1", its value is 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1. We want to apply operations so that the new expression evaluates to 0.

The cost of changing the final value of an expression is the number of operations performed on the expression. The types of operations are described as follows:

Turn a '1' into a '0'.
Turn a '0' into a '1'.
Turn a '&' into a '|'.
Turn a '|' into a '&'.

Note: '&' does not take precedence over '|' in the order of calculation. Evaluate parentheses first, then in left-to-right order.

Example 1:

Input: expression = "1&(0|1)"
Output: 1
Explanation: We can turn "1&(0|1)" into "1&(0&1)" by changing the '|' to a '&' using 1 operation.
The new expression evaluates to 0.

Example 2:

Input: expression = "(0&0)&(0&0&0)"

Output: 3

Explanation: We can turn "(0&0)&(0&0&0)" into "(0|1)|(0&0&0)" using 3 operations.

The new expression evaluates to 1.

Example 3:

Input: expression = "(0|(1|0&1))"
Output: 1
Explanation: We can turn "(0|(1|0&1))" into "(0|(0|0&1))" using 1 operation.
The new expression evaluates to 0.

Constraints:

1 <= expression.length <= 10⁵
expression only contains '1','0','&','|','(', and ')'
All parentheses are properly matched.
There will be no empty parentheses (i.e: "()" is not a substring of expression).

Solution: DP, Recursion / Simulation w/ Stack

For each expression, stores the min cost to change value to 0 and 1.

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

C++

class Solution {

public:

int minOperationsToFlip(string expression) {

stack<array<int, 3>> s;

s.push({0, 0, 0});

for (char e : expression) {

if (e == '(')

s.push({0, 0, 0});

else if (e == '&' || e == '|')

s.top()[2] = e;

else {

if (isdigit(e)) s.push({e != '0', e != '1', 0});

auto [r0, r1, _] = s.top(); s.pop();

auto [l0, l1, op] = s.top(); s.pop();

if (op == '&') {

s.push({min(l0, r0),

min(l1 + r1, min(l1, r1) + 1),

0});

} else if (op == '|') {

s.push({min(l0 + r0, min(l0, r0) + 1),

min(l1, r1),

0});

} else {

s.push({r0, r1, 0});

}

return max(s.top()[0], s.top()[1]);

}

};

花花酱 LeetCode 1895. Largest Magic Square

By zxi on August 9, 2021

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

Example 1:

Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Output: 3
Explanation: The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12

Example 2:

Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁶

Solution: Brute Force w/ Prefix Sum

Compute the prefix sum for each row and each column.

And check all possible squares.

Time complexity: O(m*n*min(m,n)²)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

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

const int m = grid.size();

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

vector<vector<int>> rows(m, vector<int>(n + 1));

vector<vector<int>> cols(n, vector<int>(m + 1));

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

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

rows[i][j + 1] = rows[i][j] + grid[i][j];

cols[j][i + 1] = cols[j][i] + grid[i][j];

}

for (int k = min(m, n); k >= 2; --k)

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

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

vector<int> s;

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

s.push_back(rows[i + r][j + k] - rows[i + r][j]);

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

s.push_back(cols[j + c][i + k] - cols[j + c][i]);

int d1 = 0;

int d2 = 0;

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

d1 += grid[i + d][j + d];

d2 += grid[i + d][j + k - d - 1];

}

s.push_back(d1);

s.push_back(d2);

if (count(begin(s), end(s), s[0]) == s.size()) return k;

}

return 1;

}

};

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

By zxi on August 9, 2021

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk.

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Constraints:

chalk.length == n
1 <= n <= 10⁵
1 <= chalk[i] <= 10⁵
1 <= k <= 10⁹

Solution: Math

Sum up all the students. k %= sum to skip all the middle rounds.

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

C++

// Author: Huahua

class Solution {

public:

int chalkReplacer(vector<int>& chalk, int k) {

long sum = accumulate(begin(chalk), end(chalk), 0L);

k %= sum;

for (size_t i = 0; i < chalk.size(); ++i)

if ((k -= chalk[i]) < 0) return i;

return -1;

}

};

花花酱 LeetCode 1893. Check if All the Integers in a Range Are Covered

By zxi on August 9, 2021

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [start_i, end_i] represents an inclusive interval between start_i and end_i.

Return true if each integer in the inclusive range [left, right] is covered by at least one interval in ranges. Return false otherwise.

An integer x is covered by an interval ranges[i] = [start_i, end_i] if start_i <= x <= end_i.

Example 1:

Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
Output: true
Explanation: Every integer between 2 and 5 is covered:
- 2 is covered by the first range.
- 3 and 4 are covered by the second range.
- 5 is covered by the third range.

Example 2:

Input: ranges = [[1,10],[10,20]], left = 21, right = 21
Output: false
Explanation: 21 is not covered by any range.

Constraints:

1 <= ranges.length <= 50
1 <= start_i <= end_i <= 50
1 <= left <= right <= 50

Solution 1: Hashtable

Time complexity: O(n * (right – left))
Space complexity: O(right – left)

C++

// Author: Huahua

class Solution {

public:

bool isCovered(vector<vector<int>>& ranges, int left, int right) {

unordered_set<int> s;

for (const auto& range : ranges)

for (int i = max(left, range[0]); i <= min(right, range[1]); ++i)

s.insert(i);

return s.size() == right - left + 1;

}

};

花花酱 LeetCode 1889. Minimum Space Wasted From Packaging

By zxi on August 9, 2021

You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.

The package sizes are given as an integer array packages, where packages[i] is the size of the i^th package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the j^th supplier produces.

You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.

For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.

Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.

Example 2:

Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.

Example 3:

Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.

Constraints:

n == packages.length
m == boxes.length
1 <= n <= 10⁵
1 <= m <= 10⁵
1 <= packages[i] <= 10⁵
1 <= boxes[j].length <= 10⁵
1 <= boxes[j][k] <= 10⁵
sum(boxes[j].length) <= 10⁵
The elements in boxes[j] are distinct.

Solution: Greedy + Binary Search

sort packages and boxes
for each box find all (unpacked) packages that are smaller or equal to itself.

Time complexity: O(nlogn) + O(mlogm) + O(mlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {

constexpr int kMod = 1e9 + 7;

const int n = packages.size();

sort(begin(packages), end(packages));

const auto bit = begin(packages);

const auto eit = end(packages);

long sum = accumulate(bit, eit, 0L);

long ans = LLONG_MAX;

for (auto& box : boxes) {

sort(begin(box), end(box));

int l = 0;

long cur = 0;

for (long b : box) {

int r = upper_bound(bit + l, eit, b) - bit;

cur += b * (r - l);

if (r == n) {

ans = min(ans, cur - sum);

break;

}

l = r;

}

return ans == LLONG_MAX ? -1 : ans % kMod;

}

};

Huahua's Tech Road

花花酱 LeetCode 1896. Minimum Cost to Change the Final Value of Expression

Solution: DP, Recursion / Simulation w/ Stack

C++

花花酱 LeetCode 1895. Largest Magic Square

Solution: Brute Force w/ Prefix Sum

C++

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

Solution: Math

C++

花花酱 LeetCode 1893. Check if All the Integers in a Range Are Covered

Solution 1: Hashtable

C++

花花酱 LeetCode 1889. Minimum Space Wasted From Packaging

Solution: Greedy + Binary Search

C++