Huahua’s Tech Road

花花酱 LeetCode 1728. Cat and Mouse II

By zxi on January 17, 2021

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

Players are represented by the characters 'C'(Cat),'M'(Mouse).
Floors are represented by the character '.' and can be walked on.
Walls are represented by the character '#' and cannot be walked on.
Food is represented by the character 'F' and can be walked on.
There is only one of each character 'C', 'M', and 'F' in grid.

Mouse and Cat play according to the following rules:

Mouse moves first, then they take turns to move.
During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
Staying in the same position is allowed.
Mouse can jump over Cat.

The game can end in 4 ways:

If Cat occupies the same position as Mouse, Cat wins.
If Cat reaches the food first, Cat wins.
If Mouse reaches the food first, Mouse wins.
If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.

Example 1:

Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
Output: true
Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 4
Output: true

Example 3:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
Output: false

Example 4:

Input: grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
Output: false

Example 5:

Input: grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
Output: true

Constraints:

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
There is only one of each character 'C', 'M', and 'F' in grid.
1 <= catJump, mouseJump <= 8

Solution: MinMax + Memoization

Time complexity: O(m^3 * n^3 * max(n, m))
Space complexity: O(m^3 * n^3)

state: [mouse_pos, cat_pos, turn]

C++

// Author: Huahua

class Solution {

public:

bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {

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

int mouse, cat, food;

for (int pos = 0; pos < m * n; ++pos)

switch (grid[pos / n][ pos % n]) {

case 'M': mouse = pos; break;

case 'C': cat = pos; break;

case 'F': food = pos; break;

default: break;

}

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

const int limit = m * n * 2;

vector<vector<vector<int>>> seen(m*n,

vector<vector<int>>(m*n, vector<int>(limit + 1, -1)));

function<bool(int, int, int)> dfs =

[&](int mouse, int cat, int d) -> bool {

const bool isCat = d & 1;

if (cat == food || cat == mouse || d >= limit) return isCat;

if (mouse == food) return !isCat;

int& ans = seen[mouse][cat][d];

if (ans != -1) return ans;

const int cur = isCat ? cat : mouse;

const int jumps = isCat ? catJump : mouseJump;

for (const auto& [dx, dy] : dirs)

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

const int x = (cur % n) + dx * j;

const int y = (cur / n) + dy * j;

const int pos = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == '#') break;

if (!dfs(isCat ? mouse : pos, isCat ? pos : cat, d + 1)) return ans = true;

}

return ans = false;

};

return dfs(mouse, cat, 0);

}

};

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

By zxi on January 17, 2021

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Example 4:

Input: matrix = [[0,0],[0,0]]
Output: 0
Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is 0 or 1.

Solution: DP + Sorting

Preprocess each column, for col j, matrix[i][j] := length consecutive ones of col j.

[0,0,1]    [0,0,1]
[1,1,1] => [1,1,2]
[1,0,1]    [2,0,3]

Then we enumerate ending row, for each ending row i, we sort row[i] in deceasing order

e.g. i = 2

[0,0,1]                  [-,-,-]
[1,1,2] sort by row 2 => [-,-,-]
[2,0,3]                  [3,2,0]

row[2][1] = 3, means there is a 3×1 all ones sub matrix, area = 3
row[2][2] = 2, means there is a 2×2 all ones sub matrix, area = 4.

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

C++

// Author: Huahua

class Solution {

public:

int largestSubmatrix(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

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

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

if (matrix[i][j]) matrix[i][j] += matrix[i - 1][j];

int ans = 0;

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

sort(rbegin(matrix[i]), rend(matrix[i]));

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

ans = max(ans, (j + 1) * matrix[i][j]);

}

return ans;

}

};

花花酱 LeetCode 1726. Tuple with Same Product

By zxi on January 17, 2021

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valids tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Example 3:

Input: nums = [2,3,4,6,8,12]
Output: 40

Example 4:

Input: nums = [2,3,5,7]
Output: 0

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁴
All elements in nums are distinct.

Solution: HashTable

Similar idea to 花花酱 LeetCode 1. Two Sum

Use a hashtable to store all the pair product counts.

Enumerate all possible pairs, increase the answer by the same product counts * 8.

Why time 8? C(4,1) * C(1,1) * C(2,1) * C(1,1)

For pair one AxB, A can be placed at any position in a four tuple, B’s position is then fixed. For another pair CxD, C has two positions to choose from, D is fixed.

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

C++

// Author: Huahua

class Solution {

public:

int tupleSameProduct(vector<int>& nums) {

const int n = nums.size();

unordered_map<int, int> m;

int ans = 0;

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

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

ans += 8 * m[nums[i] * nums[j]]++;

return ans;

}

};

花花酱 LeetCode 1725. Number Of Rectangles That Can Form The Largest Square

By zxi on January 17, 2021

You are given an array rectangles where rectangles[i] = [l_i, w_i] represents the i^th rectangle of length l_i and width w_i.

You can cut the i^th rectangle to form a square with a side length of k if both k <= l_i and k <= w_i. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

Example 2:

Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3

Constraints:

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= l_i, w_i <= 10⁹
l_i != w_i

Solution: Running Max of Shortest Edge

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

C++

// Author: Huahua

class Solution {

public:

int countGoodRectangles(vector<vector<int>>& rectangles) {

int cur = 0;

int ans = 0;

for (const auto& r : rectangles) {

if (min(r[0], r[1]) > cur) {

cur = min(r[0], r[1]);

ans = 0;

}

if (min(r[0], r[1]) == cur) ++ans;

}

return ans;

}

};

花花酱 LeetCode 1723. Find Minimum Time to Finish All Jobs

By zxi on January 10, 2021

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Solution 1: All subsets

dp[i][t] := min of max working time by assigning a subset of jobs s to the first i workers.

dp[i][t] = min{max(dp[i – 1][s], cost[s ^ t])} where s is a subset of t.

Time complexity: O(k*3^n)
Space complexity: O(k*2^n)

C++

// Author: Huahua

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

const int n = jobs.size();

int dp[13][4096];

memset(dp, 0x7f, sizeof(dp));

dp[0][0] = 0;

vector<int> cost(1 << n);

for (int t = 0; t < 1 << n; ++t) {

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

if (t >> j & 1) cost[t] += jobs[j];

dp[1][t] = cost[t]; // do jobs t by one worker

}

for (int i = 2; i <= k; ++i)

for (int t = 0; t < 1 << n; ++t)

for (int s = t; s; s = (s - 1) & t)

dp[i][t] = min(dp[i][t], max(dp[i - 1][s], cost[t ^ s]));

return dp[k][(1 << n) - 1];

}

};

Solution 2: Search + Pruning

Time complexity: O(k^n)
Space complexity: O(k*n)

C++

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

vector<int> times(k);

int ans = INT_MAX;

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

if (cur >= ans) return;

if (i == jobs.size()) {

ans = cur;

return;

}

unordered_set<int> seen;

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

if (!seen.insert(times[j]).second) continue;

times[j] += jobs[i];

dfs(i + 1, max(cur, times[j]));

times[j] -= jobs[i];

}

};

sort(rbegin(jobs), rend(jobs));

dfs(0, 0);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1728. Cat and Mouse II

Solution: MinMax + Memoization

C++

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

Solution: DP + Sorting

C++

花花酱 LeetCode 1726. Tuple with Same Product

Solution: HashTable

C++

花花酱 LeetCode 1725. Number Of Rectangles That Can Form The Largest Square

Solution: Running Max of Shortest Edge

C++

花花酱 LeetCode 1723. Find Minimum Time to Finish All Jobs

Solution 1: All subsets

C++

Solution 2: Search + Pruning

C++