2234. Maximum Total Beauty of the Gardens
Problem Description
Alice is in charge of n gardens, with a given number of flowers already planted in each one. She can plant additional flowers, up to a given number, and wants to achieve the greatest total beauty across all her gardens. A garden's beauty is dependent on whether it is 'complete' or 'incomplete'. A garden is considered 'complete' if it has at least a certain number of flowers (target). The total beauty is the sum of the number of complete gardens, each counting for a certain value (full), plus the number of flowers in the least flowered incomplete garden, counting for a different value (partial). The task is to calculate the maximum possible total beauty Alice can achieve by planting the new flowers optimally across the gardens.
Intuition
Understanding that we want to maximize the total beauty implies we should aim to make as many gardens as possible 'complete', and then focus on maximizing the beauty of the 'incomplete' gardens. To get there, the first step is to sort the gardens based on the number of flowers already planted. This allows us to see which gardens are closest to becoming complete and how we should distribute the new flowers.
Next, we iteratively try to calculate the total beauty starting from the scenario where all gardens are incomplete to the one where all are complete (that we can achieve given the constraints). At each step, we subtract the flowers we need to plant in the last garden to reach the target if it's not already complete.
For each iteration, we then determine how to best allocate remaining new flowers to incomplete gardens. The best allocation is the one that increases the minimum flower count in incomplete gardens, which directly contributes to the total beauty score regarding the partial value. This step employs binary search to efficiently find the point at which we can maximize the incomplete garden's beauty without exceeding the remaining new flowers.
The answer to our problem is the largest total beauty we can calculate in one of the iterations. This solution balances between making gardens complete and enhancing the beauty of incomplete ones, always trying to use the available resources (newFlowers) wisely.
Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Solution Approach
The implementation begins with sorting the flowers array in non-decreasing order. This helps us to identify which gardens are closer to being 'complete'.
An important part of the algorithm is the prefix sum array, s, which is computed using the accumulate function. Prefix sum arrays allow for constant-time queries of the sum of a subarray, which is essential for calculating the required number of new flowers efficiently.
Using the binary search algorithm, realized by the bisect_left method, it identifies how many gardens are already complete, starting from those requiring the fewest additional flowers to reach the target.
We iterate over the possible number of complete gardens, decrementing the newFlowers count by the number required to reach the target for the currently considered garden to become complete. This is done by checking if newFlowers would go negative after the operation, which indicates that no more flowers can be planted and consequently breaks the loop.
For the 'incomplete' gardens, a binary search is employed within the loop to find the highest value y such that all gardens below index l can have at least y flowers without using more than the available newFlowers. This is calculated by comparing the cost to bring all gardens up to a certain flower count mid with the remaining newFlowers.
The condition flowers[mid] * (mid + 1) - s[mid + 1] calculates the total number of flowers needed to bring all gardens up to flower count mid. By comparing this to newFlowers, we either set l = mid or r = mid - 1 depending on whether we can afford to bring all gardens up to flower count mid or not.
The maximum value of y is calculated with the formula min(flowers[l] + (newFlowers - cost) // (l + 1), target - 1). It determines the maximum number of flowers we can distribute amongst incomplete gardens to maximize their individual 'incomplete' beauty, without exceeding either newFlowers or making the garden complete.
Finally, for each possible number of complete gardens, we update ans to keep the maximum total beauty, which is a combination of x * full (total beauty from complete gardens) and y * partial (total beauty from the least flowered incomplete garden).
This approach relies heavily on sorting, prefix sums, and binary search algorithms to efficiently compute the maximum total beauty for Alice's gardens.
Which algorithm should you use to find a node that is close to the root of the tree?
Example Walkthrough
Let's use a simple example to illustrate the solution approach described above. Assume Alice is in charge of n = 3 gardens with the following number of flowers already planted: [1, 3, 5]. She has newFlowers = 4 that she can plant, and we're given the following:
targetvalue (to consider a garden complete):6fullvalue (each complete garden's beauty):10partialvalue (beauty value of the least flowered incomplete garden):2
Firstly, we sort the flowers array, which in this case is already sorted: [1, 3, 5].
Next, we create a prefix sum array s.
prefix sum = [0, 1, 4, 9](adding a leading zero for ease of calculations)
Now, we need to calculate the maximum total beauty. We start by considering how many gardens can be made complete. Since we want to make as many gardens complete as possible, we look at the smallest number and see if we can reach the target by planting new flowers.
Iteration 1: No Complete Gardens
- At first, all gardens are incomplete.
- We see if we can use the
newFlowersto increase the beauty of the incomplete gardens. - Counting the least flowered garden, we can plant all
newFlowersthere:1 + 4 = 5(still incomplete). - The maximum total beauty at this point is
0 * 10 + 5 * 2 = 0 + 10 = 10
Iteration 2: Attempt to Make the First Garden Complete
- We check if we can make the first garden complete by subtracting
6 - 1 = 5new flowers, which is more than we have, so we can't make any garden complete. - Since we can't complete any garden, the previous calculation still holds, and
10is still our maximum total beauty.
Iteration 3: Attempt to Complete the Second Garden
- We would need
6 - 3 = 3new flowers to make the second garden complete, and we have enough to do that. - After planting those flowers, we are left with
4 - 3 = 1new flower. - The first garden is now our least flowered incomplete garden, and we can plant the last new flower there:
1 + 1 = 2. - However, making the second garden complete yields a lower total beauty than our current max (
1 * 10 + 2 * 2 = 10 + 4 = 14), so we do not update our maximum total beauty.
Iteration 4: Attempt to Complete the Third Garden
- We would need
6 - 5 = 1new flower to make the third garden complete, and we have enough to do that. - After making the third garden complete, we are left with
4 - 1 = 3new flowers to distribute. - If we distribute those to the first two gardens, the second one becomes incomplete with the most flowers.
- This will give us a total beauty of
1 * 10 + 3 * 2 = 10 + 6 = 16, which becomes our new maximum total beauty.
With the above steps, we arrive at the conclusion that the maximum possible total beauty Alice can achieve is 16, by making the third garden complete and maximizing the flowers in the second, least flowered incomplete garden.
Note: This walkthrough is a simplified version using low numbers for easy understanding. The actual solution approach uses binary search within each step to handle larger input sizes efficiently.
Solution Implementation
1from bisect import bisect_left
2from itertools import accumulate
3
4
5class Solution:
6 def maximum_beauty(self, flowers, new_flowers, target, full, partial):
7 # Sort the flowers array to ease finding the flowers with the beauty value below target.
8 flowers.sort()
9 n = len(flowers)
10
11 # Calculate prefix sum to use it later for finding the total flowers needed.
12 prefix_sum = list(accumulate(flowers, initial=0))
13
14 # Initial answer is set to 0.
15 ans = 0
16
17 # Find the starting index of flowers at or above the target
18 flowers_above_target = n - bisect_left(flowers, target)
19
20 # Loop to calculate the maximum beauty.
21 for x in range(flowers_above_target, n + 1):
22 # Decrease the new flowers count by the amount needed to bring the
23 # last x flowers up to the target or by 0 if no flowers need to be increased.
24 new_flowers -= max(target - flowers[n - x], 0) if x > 0 else 0
25
26 # Break out of the loop if there are not enough new flowers.
27 if new_flowers < 0:
28 break
29
30 # Binary search to find the highest beauty achievable for non-full flowers.
31 left, right = 0, n - x - 1
32 while left < right:
33 mid = (left + right + 1) >> 1
34 if flowers[mid] * (mid + 1) - prefix_sum[mid + 1] <= new_flowers:
35 left = mid
36 else:
37 right = mid - 1
38
39 # Calculate the possible beauty value for non-full flowers.
40 beauty = 0
41 if right != -1:
42 cost = flowers[left] * (left + 1) - prefix_sum[left + 1]
43 beauty = min(flowers[left] + (new_flowers - cost) // (left + 1), target - 1)
44
45 # Update the answer if the current combination of full and partial flowers
46 # has higher beauty than previously calculated answers.
47 ans = max(ans, x * full + beauty * partial)
48
49 return ans
501import java.util.Arrays;
2
3class Solution {
4 public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
5 Arrays.sort(flowers); // Sort the flowers array.
6 int flowersCount = flowers.length; // Store the number of flowers.
7 long[] prefixSums = new long[flowersCount + 1]; // Create a prefix sums array.
8 // Calculate the prefix sums of flowers.
9 for (int i = 0; i < flowersCount; ++i) {
10 prefixSums[i + 1] = prefixSums[i] + flowers[i];
11 }
12 long maxBeauty = 0; // The maximum beauty that can be achieved.
13 int fullBloomFlowers = 0; // Counter for flowers at or above the target number.
14 // Count flowers that have already reached the target.
15 for (int flower : flowers) {
16 if (flower >= target) {
17 ++fullBloomFlowers;
18 }
19 }
20 // Start calculating maximum beauty for different scenarios.
21 for (; fullBloomFlowers <= flowersCount; ++fullBloomFlowers) {
22 // Calculate remaining new flowers after making full bloom flowers reach target.
23 newFlowers -= (fullBloomFlowers == 0 ? 0 : Math.max(target - flowers[flowersCount - fullBloomFlowers], 0));
24 if (newFlowers < 0) {
25 break; // If we don't have enough new flowers, break the loop.
26 }
27 int left = 0, right = flowersCount - fullBloomFlowers - 1;
28 // Binary search to find the maximum flower count in partial bloom under budget.
29 while (left < right) {
30 int mid = (left + right + 1) >>> 1;
31 if ((long) flowers[mid] * (mid + 1) - prefixSums[mid + 1] <= newFlowers) {
32 left = mid;
33 } else {
34 right = mid - 1;
35 }
36 }
37 // The maximum beauty for the flowers that are in partial bloom.
38 long partialMax = 0;
39 if (right != -1) {
40 long cost = (long) flowers[left] * (left + 1) - prefixSums[left + 1];
41 partialMax = Math.min(flowers[left] + (newFlowers - cost) / (left + 1), target - 1);
42 }
43 // Update maxBeauty with the larger value between current max and new possibility.
44 maxBeauty = Math.max(maxBeauty, (long) fullBloomFlowers * full + partialMax * partial);
45 }
46 return maxBeauty; // Return the maximum beauty calculated.
47 }
48}
491#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 long long maximumBeauty(std::vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
7 // Sort the flowers array in non-decreasing order.
8 std::sort(flowers.begin(), flowers.end());
9
10 int flowersCount = flowers.size();
11 // Prefix sum array to store the sum of flowers till the ith index.
12 std::vector<long long> prefixSum(flowersCount + 1, 0);
13
14 // Precompute the prefix sums.
15 for (int i = 1; i <= flowersCount; ++i) {
16 prefixSum[i] = prefixSum[i - 1] + flowers[i - 1];
17 }
18
19 long long maxBeauty = 0; // Variable to store the maximum beauty of the garden.
20
21 // Find the position from where all flowers are already at least the target height.
22 int aboveTargetCount = flowers.end() - std::lower_bound(flowers.begin(), flowers.end(), target);
23
24 // Try each possible x, the number of totally bloomed flowers, and calculate the maximum partial beauty for the rest.
25 for (int x = aboveTargetCount; x <= flowersCount; ++x) {
26 newFlowers -= (x == 0 ? 0 : std::max(target - flowers[flowersCount - x], 0));
27 if (newFlowers < 0) { // Not enough newFlowers to make x flowers reach the target height.
28 break;
29 }
30
31 // Binary search to find the maximum height we can make the shortest flower,
32 // for maximizing partial beauty, given the remaining newFlowers.
33 int left = 0, right = flowersCount - x - 1;
34
35 while (left < right) {
36 int mid = (left + right + 1) >> 1;
37
38 // Calculate if we can make all flowers up to index mid reach the height of flowers[mid] given newFlowers.
39 if (static_cast<long long>(flowers[mid]) * (mid + 1) - prefixSum[mid + 1] <= newFlowers) {
40 left = mid;
41 } else {
42 right = mid - 1;
43 }
44 }
45
46 int maxY = 0; // Variable to store the increased height towards maximum partial beauty.
47
48 // If we have at least one flower whose height can be increased for partial beauty.
49 if (right != -1) {
50 long long cost = static_cast<long long>(flowers[left]) * (left + 1) - prefixSum[left + 1];
51 // Calculate the maximum additional height achievable for the shortest flower within leftover newFlowers.
52 long long increaseAmount = flowers[left] + (newFlowers - cost) / (left + 1);
53 long long threshold = target - 1; // We aim for one less than the target height for partial beauty.
54 maxY = std::min(increaseAmount, threshold);
55 }
56
57 // Calculate the current beauty with x fully bloomed and the rest partially bloomed.
58 maxBeauty = std::max(maxBeauty, static_cast<long long>(x) * full + static_cast<long long>(maxY) * partial);
59 }
60
61 // Return the maximum beauty calculated.
62 return maxBeauty;
63 }
64};
651function maximumBeauty(
2 flowers: number[],
3 newFlowers: number,
4 target: number,
5 full: number,
6 partial: number,
7): number {
8 // Sort the flower array in non-decreasing order
9 flowers.sort((a, b) => a - b);
10
11 // Determine the number of flower beds
12 const numBeds = flowers.length;
13
14 // Initialize an array to store the prefix sums of flowers
15 const prefixSums: number[] = Array(numBeds + 1).fill(0);
16 for (let i = 1; i <= numBeds; i++) {
17 prefixSums[i] = prefixSums[i - 1] + flowers[i - 1];
18 }
19
20 // Count the number of flower beds that are already at or above the target beauty level
21 let countAtTarget = flowers.filter(flower => flower >= target).length;
22
23 // Initialize an answer variable to store the maximum beauty
24 let maxBeauty = 0;
25
26 // Iterate through possible values for the number of full-bloomed flower beds
27 for (; countAtTarget <= numBeds; ++countAtTarget) {
28 // Decrease the number of new flowers by the amount needed to bring the current bed to target
29 newFlowers -= countAtTarget === 0 ? 0 : Math.max(target - flowers[numBeds - countAtTarget], 0);
30
31 // Exit the loop if there are not enough new flowers left
32 if (newFlowers < 0) {
33 break;
34 }
35
36 // Use binary search to determine the best achievable partial beauty in remaining beds
37 let left = 0;
38 let right = numBeds - countAtTarget - 1;
39 while (left < right) {
40 const mid = (left + right + 1) >> 1;
41 if (flowers[mid] * (mid + 1) - prefixSums[mid + 1] <= newFlowers) {
42 left = mid;
43 } else {
44 right = mid - 1;
45 }
46 }
47
48 let partialBeauty = 0;
49 if (right !== -1) {
50 // Calculate the cost to make left number of beds the same beauty level
51 const cost = flowers[left] * (left + 1) - prefixSums[left + 1];
52 // Calculate the maximum beauty level achievable for a partially completed bed
53 partialBeauty = Math.min(
54 flowers[left] + Math.floor((newFlowers - cost) / (left + 1)),
55 target - 1
56 );
57 }
58
59 // Update maxBeauty if the current configuration yields higher beauty
60 maxBeauty = Math.max(maxBeauty, countAtTarget * full + partialBeauty * partial);
61 }
62
63 return maxBeauty;
64}
65How many ways can you arrange the three letters A, B and C?
Time and Space Complexity
Time Complexity
The given algorithm primarily contains the following steps:
- Sorting the flowers array, which has a time complexity of
O(n log n)wherenis the number of elements in the flowers array. - Searching for the index i using a binary search approach, specifically the
bisect_leftfunction. The complexity for this step isO(log n). - Iterating over a range from
itonwhich is at mostniterations. - Within the loop, performing another binary search in the worst case on the entire list which again adds up to a
O(log n)complexity for each iteration of the loop. - Calculating the maximum beauty in constant time
O(1)once for each iteration of the loop.
Considering that the binary search is within a loop of n iterations, the two binary search operations contribute O(n log n) together. Therefore, the overall time complexity is dominated by these two operations and can be approximated as O(n log n).
Space Complexity
The algorithm uses additional space for:
- The sorted version of the input flowers list, which requires
O(n)space. - The prefix sum list
s, which is alsoO(n). - A few constant-size variables, which contribute
O(1).
Thus, the total space complexity of the algorithm is O(n) since the n-sized additional data structures dominate over the constant-sized variables.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.