2234. Maximum Total Beauty of the Gardens

HardGreedyArrayTwo PointersBinary SearchSorting

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.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

target value (to consider a garden complete): 6
full value (each complete garden's beauty): 10
partial value (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 newFlowers to increase the beauty of the incomplete gardens.
Counting the least flowered garden, we can plant all newFlowers there: 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 = 5 new 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 10 is still our maximum total beauty.

Iteration 3: Attempt to Complete the Second Garden

We would need 6 - 3 = 3 new flowers to make the second garden complete, and we have enough to do that.
After planting those flowers, we are left with 4 - 3 = 1 new 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 = 1 new 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 = 3 new 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
50

1import 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}
49

1#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};
65

1function 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}
65

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) where n is the number of elements in the flowers array.
Searching for the index i using a binary search approach, specifically the bisect_left function. The complexity for this step is O(log n).
Iterating over a range from i to n which is at most n iterations.
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 also O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know