Posts tagged as “medium”

花花酱 LeetCode 1765. Map of Highest Peak

By zxi on February 20, 2021

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.
If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

The height of each cell must be non-negative.
If the cell is a water cell, its height must be 0.
Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)‘s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] is 0 or 1.
There is at least one water cell.

Solution: BFS

h[y][x] = min distance of (x, y) to any water cell.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {

const int m = isWater.size();

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

vector<vector<int>> ans(m, vector<int>(n, INT_MIN));

queue<pair<int, int>> q;

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

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

if (isWater[y][x]) {

q.emplace(x, y);

ans[y][x] = 0;

}

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

while (!q.empty()) {

const auto [cx, cy] = q.front();

q.pop();

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

const int x = cx + dirs[i];

const int y = cy + dirs[i + 1];

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

if (ans[y][x] != INT_MIN) continue;

ans[y][x] = ans[cy][cx] + 1;

q.emplace(x, y);

}

return ans;

}

};

花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag

By zxi on February 13, 2021

You are given an integer array nums where the i^th bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

Take any bag of balls and divide it into two new bags with a positive number of balls.
- For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

Example 1:

Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2 an you should return 2.

Example 3:

Input: nums = [7,17], maxOperations = 2
Output: 7

Constraints:

1 <= nums.length <= 10⁵
1 <= maxOperations, nums[i] <= 10⁹

Solution: Binary Search

Find the smallest penalty that requires less or equal ops than max_ops.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSize(vector<int>& nums, int maxOperations) {

int l = 1, r = *max_element(begin(nums), end(nums));

while (l < r) {

const int m = l + (r - l) / 2;

int count = 0;

for (int x : nums)

count += (x - 1) / m;

if (count <= maxOperations)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1759. Count Number of Homogenous Substrings

By zxi on February 13, 2021

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10⁹ + 7.

A string is homogenous if all the characters of the string are the same.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

Input: s = "zzzzz"
Output: 15

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase letters.

Solution: Counting

Let m be the length of the longest homogenous substring, # of homogenous substring is m * (m + 1) / 2.
e.g. aaabb
“aaa” => m = 3, # = 3 * (3 + 1) / 2 = 6
“bb” => m = 2, # = 2 * (2+1) / 2 = 3
Total = 6 + 3 = 9

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

C++

// Author: Huahua

class Solution {

public:

int countHomogenous(string s) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

long ans = 0;

for (long i = 0, j = 0; i < n; i = j) {

while (j < n && s[i] == s[j]) ++j;

ans += (j - i) * (j - i + 1) / 2;

}

return ans % kMod;

}

};

花花酱 LeetCode 1754. Largest Merge Of Two Strings

By zxi on February 7, 2021

You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:

If word1 is non-empty, append the first character in word1 to merge and delete it from word1.
- For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
- For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".

Return the lexicographically largest merge you can construct.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Example 1:

Input: word1 = "cabaa", word2 = "bcaaa"
Output: "cbcabaaaaa"
Explanation: One way to get the lexicographically largest merge is:
- Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
- Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
- Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
- Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
- Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
- Append the remaining 5 a's from word1 and word2 at the end of merge.

Example 2:

Input: word1 = "abcabc", word2 = "abdcaba"
Output: "abdcabcabcaba"

Constraints:

1 <= word1.length, word2.length <= 3000
word1 and word2 consist only of lowercase English letters.

Solution: Greedy

Always take a single char from the largest word. (NOT just the current char).

E.g.
ans = “”, w1 = “cabba”, w2 = “bcaaa”
w1 > w2, take from w1
ans = “c”, w1 = “abba”, w2 = “bcaaa”
w1 < w2, take from w2
ans = “cb”, w1 = “abba”, w2 = “caaa”
w1 < w2, take from w2
ans = “cbc”, w1 = “abba”, w2 = “aaa”
w1 > w2, take from w1. Note: both start with “a”, but we need to compare the entire word.
ans = “cbca”, w1 = “bba”, w2 = “aaa”
w1 > w2, take from w1
ans = “cbcab”, w1 = “ba”, w2 = “aaa”
…

Time complexity: O(min(m,n)^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string largestMerge(string_view w1, string_view w2) {

string ans;

int m = w1.length(), n = w2.length();

int i = 0, j = 0;

while (i < m && j < n)

ans += w1.substr(i) > w2.substr(j) ? w1[i++] : w2[j++];

ans.append(w1.substr(i));

ans.append(w2.substr(j));

return ans;

}

};

花花酱 LeetCode 1753. Maximum Score From Removing Stones

By zxi on February 7, 2021

You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a, b, and c, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:
- Take from 1st and 3rd piles, state is now (1, 4, 5)
- Take from 1st and 3rd piles, state is now (0, 4, 4)
- Take from 2nd and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: The starting state is (4, 4, 6). One optimal set of moves is:
- Take from 1st and 2nd piles, state is now (3, 3, 6)
- Take from 1st and 3rd piles, state is now (2, 3, 5)
- Take from 1st and 3rd piles, state is now (1, 3, 4)
- Take from 1st and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.
After that, there are fewer than two non-empty piles, so the game ends.

Constraints:

1 <= a, b, c <= 10⁵

Solution 1: Greedy

Take two stones (one each) from the largest two piles, until one is empty.

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

C++

class Solution {

public:

int maximumScore(int a, int b, int c) {

array<int, 3> s{a,b,c};

sort(begin(s), end(s));

int ans = 0;

while (s[1]-- && s[2]--) {

++ans;

sort(begin(s), end(s));

}

return ans;

}

};

Solution 2: Math

First, let’s assuming a <= b <= c.
There are two conditions:
1. a + b <= c, we can pair c with a first and then b. Total pairs is (a + b + (a + b)) / 2
2. a + b > c, we can pair c with a, b “evenly”, and then pair a with b, total pairs is (a + b + c) / 2

ans = (a + b + min(a + b, c)) / 2

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

C++

class Solution {

public:

int maximumScore(int a, int b, int c) {

array<int, 3> s{a,b,c};

sort(begin(s), end(s));

return (s[0] + s[1] + min(s[0] + s[1], s[2])) / 2;

}

};