2234. Maximum Total Beauty of the Gardens LeetCode Solution
In this guide, you will get 2234. Maximum Total Beauty of the Gardens LeetCode Solution with the best time and space complexity. The solution to Maximum Total Beauty of the Gardens problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Total Beauty of the Gardens
Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens.
You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the ith garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers target, full, and partial.
A garden is considered complete if it has at least target flowers. The total beauty of the gardens is then determined as the sum of the following:
The number of complete gardens multiplied by full.
The minimum number of flowers in any of the incomplete gardens multiplied by partial. If there are no incomplete gardens, then this value will be 0.
Return the maximum total beauty that Alice can obtain after planting at most newFlowers flowers.
Example 1:
Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
Output: 14
Explanation: Alice can plant
– 2 flowers in the 0th garden
– 3 flowers in the 1st garden
– 1 flower in the 2nd garden
– 1 flower in the 3rd garden
The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers.
There is 1 garden that is complete.
The minimum number of flowers in the incomplete gardens is 2.
Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14.
No other way of planting flowers can obtain a total beauty higher than 14.
Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
Output: 30
Explanation: Alice can plant
– 3 flowers in the 0th garden
– 0 flowers in the 1st garden
– 0 flowers in the 2nd garden
– 2 flowers in the 3rd garden
The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers.
There are 3 gardens that are complete.
The minimum number of flowers in the incomplete gardens is 4.
Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30.
No other way of planting flowers can obtain a total beauty higher than 30.
Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.
2234. Maximum Total Beauty of the Gardens LeetCode Solution in C++
class Solution {
public:
long long maximumBeauty(vector<int>& flowers, long long newFlowers,
int target, int full, int partial) {
const int n = flowers.size();
// If a garden is already complete, clamp it to the target.
for (int& flower : flowers)
flower = min(flower, target);
ranges::sort(flowers);
// All gardens are complete, so nothing we can do.
if (flowers[0] == target)
return static_cast<long>(n) * full;
// Having many new flowers maximizes the beauty value.
if (newFlowers >= static_cast<long>(n) * target -
accumulate(flowers.begin(), flowers.end(), 0L))
return max(static_cast<long>(n) * full,
(n - 1L) * full + (target - 1L) * partial);
long ans = 0;
long leftFlowers = newFlowers;
// cost[i] := the cost to make flowers[0..i] the same
vector<long> cost(n);
for (int i = 1; i < n; ++i)
// Plant (flowers[i] - flowers[i - 1]) flowers for flowers[0..i - 1].
cost[i] =
cost[i - 1] + static_cast<long>(i) * (flowers[i] - flowers[i - 1]);
int i = n - 1; // flowers' index (flowers[i + 1..n) are complete)
while (flowers[i] == target)
--i;
for (; leftFlowers >= 0; --i) {
// To maximize the minimum number of incomplete flowers, we find the first
// index j that we can't make flowers[0..j] equal to flowers[j], then we
// know we can make flowers[0..j - 1] equal to flowers[j - 1]. In the
// meantime, evenly increase each of them to seek a bigger minimum value.
const int j = firstGreater(cost, i, leftFlowers);
const long minIncomplete =
flowers[j - 1] + (leftFlowers - cost[j - 1]) / j;
ans = max(ans, (n - 1L - i) * full + minIncomplete * partial);
leftFlowers -= max(0, target - flowers[i]);
}
return ans;
}
private:
int firstGreater(const vector<long>& A, int maxIndex, long target) {
return upper_bound(A.begin(), A.begin() + maxIndex + 1, target) - A.begin();
}
}; /* code provided by PROGIEZ */
2234. Maximum Total Beauty of the Gardens LeetCode Solution in Java
class Solution {
public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
final int n = flowers.length;
// If a garden is already complete, clamp it to the target.
for (int i = 0; i < n; ++i)
flowers[i] = Math.min(flowers[i], target);
Arrays.sort(flowers);
// All gardens are complete, so nothing we can do.
if (flowers[0] == target)
return (long) n * full;
// Having many new flowers maximizes the beauty value.
if (newFlowers >= (long) n * target - Arrays.stream(flowers).asLongStream().sum())
return Math.max((long) n * full, (n - 1L) * full + (target - 1L) * partial);
long ans = 0;
long leftFlowers = newFlowers;
// cost[i] := the cost to make flowers[0..i] the same
long[] cost = new long[flowers.length];
for (int i = 1; i < flowers.length; ++i)
// Plant (flowers[i] - flowers[i - 1]) flowers for flowers[0..i - 1].
cost[i] = cost[i - 1] + i * (flowers[i] - flowers[i - 1]);
int i = flowers.length - 1; // flowers' index (flowers[i + 1..n) are complete)
while (flowers[i] == target)
--i;
for (; leftFlowers >= 0; --i) {
// To maximize the minimum number of incomplete flowers, we find the first
// index j that we can't make flowers[0..j] equal to flowers[j], then we
// know we can make flowers[0..j - 1] equal to flowers[j - 1]. In the
// meantime, evenly increase each of them to seek a bigger minimum value.
final int j = firstGreater(cost, i, leftFlowers);
final long minIncomplete = flowers[j - 1] + (leftFlowers - cost[j - 1]) / j;
ans = Math.max(ans, (n - 1L - i) * full + (long) minIncomplete * partial);
leftFlowers -= Math.max(0, target - flowers[i]);
}
return ans;
}
private int firstGreater(long[] A, int maxIndex, long target) {
final int i = Arrays.binarySearch(A, 0, maxIndex + 1, target + 1);
return i < 0 ? -i - 1 : i;
}
} // code provided by PROGIEZ
2234. Maximum Total Beauty of the Gardens LeetCode Solution in Python
class Solution:
def maximumBeauty(
self,
flowers: list[int],
newFlowers: int,
target: int,
full: int,
partial: int,
) -> int:
n = len(flowers)
# If a garden is already complete, clamp it to the target.
flowers = [min(flower, target) for flower in flowers]
flowers.sort()
# All gardens are complete, so nothing we can do.
if flowers[0] == target:
return n * full
# Having many new flowers maximizes the beauty value.
if newFlowers >= n * target - sum(flowers):
return max(n * full, (n - 1) * full + (target - 1) * partial)
ans = 0
leftFlowers = newFlowers
# cost[i] := the cost to make flowers[0..i] the same
cost = [0] * n
for i in range(1, n):
# Plant (flowers[i] - flowers[i - 1]) flowers for flowers[0..i - 1].
cost[i] = cost[i - 1] + i * (flowers[i] - flowers[i - 1])
i = n - 1 # flowers' index (flowers[i + 1..n) are complete)
while flowers[i] == target:
i -= 1
while leftFlowers >= 0:
# To maximize the minimum number of incomplete flowers, we find the first
# index j that we can't make flowers[0..j] equal to flowers[j], then we
# know we can make flowers[0..j - 1] equal to flowers[j - 1]. In the
# meantime, evenly increase each of them to seek a bigger minimum value.
j = min(i + 1, bisect_right(cost, leftFlowers))
minIncomplete = flowers[j - 1] + (leftFlowers - cost[j - 1]) // j
ans = max(ans, (n - 1 - i) * full + minIncomplete * partial)
leftFlowers -= max(0, target - flowers[i])
i -= 1
return ans # code by PROGIEZ
