2234. Maximum Total Beauty of the Gardens

HardGreedyArrayTwo PointersBinary SearchEnumerationPrefix SumSorting

Leetcode Link

Problem Description

Alice manages n gardens and wants to maximize their total beauty by planting additional flowers.

You're given:

An array flowers where flowers[i] represents the number of flowers already planted in garden i (these cannot be removed)
newFlowers: the maximum number of additional flowers Alice can plant
target: the minimum number of flowers needed for a garden to be considered "complete"
full: the beauty value contributed by each complete garden
partial: the beauty value multiplier for the minimum flower count among incomplete gardens

A garden is complete if it has at least target flowers. The total beauty is calculated as:

Number of complete gardens × full
Plus: Minimum flower count among all incomplete gardens × partial (or 0 if all gardens are complete)

The goal is to distribute up to newFlowers additional flowers among the gardens to maximize the total beauty.

For example, if you have 3 gardens with [1, 2, 4] flowers, target = 4, full = 5, partial = 2, and newFlowers = 3:

Garden 2 already has 4 flowers (complete)
You could add 2 flowers to garden 1 to make it complete (having 4 flowers)
This would give: 2 complete gardens × 5 + minimum of remaining incomplete gardens (2) × 2 = 10 + 4 = 14 total beauty
Alternatively, you could distribute flowers to increase the minimum among incomplete gardens for a different beauty value

The challenge is finding the optimal balance between creating more complete gardens versus increasing the minimum flower count in incomplete gardens to maximize the total beauty score.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that we face a trade-off: we can either use our additional flowers to create more complete gardens (earning full points each) or increase the minimum flower count among incomplete gardens (earning partial points per flower in the minimum garden).

First, we should sort the gardens by their current flower count. This helps us identify which gardens are easiest to complete (those closest to target) and which incomplete gardens we can efficiently boost together.

Why enumerate the number of complete gardens? Since we want to maximize beauty, we need to try different configurations. If we decide to have x complete gardens, we should complete the x gardens that already have the most flowers - this minimizes the cost and leaves more flowers for boosting incomplete gardens.

For each configuration with x complete gardens:

We complete the rightmost x gardens in our sorted array (they need the fewest additional flowers)
With the remaining flowers, we want to maximize the minimum among the incomplete gardens

The second part is clever: to maximize the minimum efficiently, we should bring all gardens up to the same level together. If we have gardens with [1, 2, 3] flowers and want to increase the minimum, we should first bring them all to 3, then all to 4, and so on. This is why we use binary search - to find the highest level we can afford to bring a group of gardens to.

The binary search finds the largest prefix of incomplete gardens we can afford to level up to the same height. The cost to bring gardens 0 to mid up to height flowers[mid] is flowers[mid] * (mid + 1) - sum(flowers[0:mid+1]). If we have extra flowers after this leveling, we can increase all these gardens further by dividing the remaining flowers equally among them.

By trying all possible values of x (number of complete gardens) and finding the optimal minimum for incomplete gardens in each case, we guarantee finding the maximum total beauty.

Learn more about Greedy, Two Pointers, Binary Search, Prefix Sum and Sorting patterns.

Solution Implementation

1class Solution:
2    def maximumBeauty(
3        self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int
4    ) -> int:
5        flowers.sort()
6        n = len(flowers)
7        prefix_sum = list(accumulate(flowers, initial=0))
8
9        max_beauty = 0
10        gardens_already_full = n - bisect_left(flowers, target)
11
12        for num_complete in range(gardens_already_full, n + 1):
13            if num_complete > 0:
14                flowers_needed = max(target - flowers[n - num_complete], 0)
15                newFlowers -= flowers_needed
16
17            if newFlowers < 0:
18                break
19
20            # Binary search using first_true_index template (inverted condition)
21            # Find first index where cost > newFlowers (too expensive)
22            incomplete_count = n - num_complete
23            left, right = 0, incomplete_count  # Extended right for edge case
24            first_true_index = incomplete_count  # Default: no index is too expensive
25
26            while left <= right:
27                mid = (left + right) // 2
28                if mid >= incomplete_count:
29                    # Out of bounds, this is too expensive
30                    first_true_index = mid
31                    right = mid - 1
32                else:
33                    cost = flowers[mid] * (mid + 1) - prefix_sum[mid + 1]
34                    if cost > newFlowers:  # Too expensive
35                        first_true_index = mid
36                        right = mid - 1
37                    else:
38                        left = mid + 1
39
40            # Maximum affordable index = first_true_index - 1
41            max_affordable_idx = first_true_index - 1
42
43            partial_level = 0
44            if max_affordable_idx >= 0:
45                base_cost = flowers[max_affordable_idx] * (max_affordable_idx + 1) - prefix_sum[max_affordable_idx + 1]
46                remaining = newFlowers - base_cost
47                partial_level = min(flowers[max_affordable_idx] + remaining // (max_affordable_idx + 1), target - 1)
48
49            beauty_score = num_complete * full + partial_level * partial
50            max_beauty = max(max_beauty, beauty_score)
51
52        return max_beauty
53

1class Solution {
2    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
3        Arrays.sort(flowers);
4        int n = flowers.length;
5
6        long[] prefixSum = new long[n + 1];
7        for (int i = 0; i < n; ++i) {
8            prefixSum[i + 1] = prefixSum[i] + flowers[i];
9        }
10
11        long maxBeauty = 0;
12        int completeGardens = 0;
13        for (int flowerCount : flowers) {
14            if (flowerCount >= target) ++completeGardens;
15        }
16
17        for (; completeGardens <= n; ++completeGardens) {
18            long flowersNeeded = (completeGardens == 0 ? 0 : Math.max(target - flowers[n - completeGardens], 0));
19            newFlowers -= flowersNeeded;
20
21            if (newFlowers < 0) break;
22
23            // Binary search using first_true_index template (inverted condition)
24            int incompleteCount = n - completeGardens;
25            int left = 0, right = incompleteCount;
26            int firstTrueIndex = incompleteCount;
27
28            while (left <= right) {
29                int mid = left + (right - left) / 2;
30                if (mid >= incompleteCount) {
31                    firstTrueIndex = mid;
32                    right = mid - 1;
33                } else {
34                    long cost = (long) flowers[mid] * (mid + 1) - prefixSum[mid + 1];
35                    if (cost > newFlowers) {  // Too expensive
36                        firstTrueIndex = mid;
37                        right = mid - 1;
38                    } else {
39                        left = mid + 1;
40                    }
41                }
42            }
43
44            int maxAffordableIdx = firstTrueIndex - 1;
45            long minIncompleteFlowers = 0;
46            if (maxAffordableIdx >= 0) {
47                long cost = (long) flowers[maxAffordableIdx] * (maxAffordableIdx + 1) - prefixSum[maxAffordableIdx + 1];
48                minIncompleteFlowers = Math.min(flowers[maxAffordableIdx] + (newFlowers - cost) / (maxAffordableIdx + 1), target - 1);
49            }
50
51            long currentBeauty = (long) completeGardens * full + minIncompleteFlowers * partial;
52            maxBeauty = Math.max(maxBeauty, currentBeauty);
53
54            newFlowers += flowersNeeded;
55        }
56
57        return maxBeauty;
58    }
59}
60

1class Solution {
2public:
3    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
4        sort(flowers.begin(), flowers.end());
5        int n = flowers.size();
6
7        vector<long long> prefixSum(n + 1, 0);
8        for (int i = 1; i <= n; ++i) {
9            prefixSum[i] = prefixSum[i - 1] + flowers[i - 1];
10        }
11
12        long long maxBeauty = 0;
13        int alreadyFull = flowers.end() - lower_bound(flowers.begin(), flowers.end(), target);
14
15        for (int numFullGardens = alreadyFull; numFullGardens <= n; ++numFullGardens) {
16            if (numFullGardens > 0) {
17                int gardenIndex = n - numFullGardens;
18                newFlowers -= max(target - flowers[gardenIndex], 0);
19            }
20
21            if (newFlowers < 0) break;
22
23            // Binary search using first_true_index template (inverted condition)
24            int incompleteCount = n - numFullGardens;
25            int left = 0, right = incompleteCount;
26            int firstTrueIndex = incompleteCount;
27
28            while (left <= right) {
29                int mid = left + (right - left) / 2;
30                if (mid >= incompleteCount) {
31                    firstTrueIndex = mid;
32                    right = mid - 1;
33                } else {
34                    long long cost = 1LL * flowers[mid] * (mid + 1) - prefixSum[mid + 1];
35                    if (cost > newFlowers) {  // Too expensive
36                        firstTrueIndex = mid;
37                        right = mid - 1;
38                    } else {
39                        left = mid + 1;
40                    }
41                }
42            }
43
44            int maxAffordableIdx = firstTrueIndex - 1;
45            long long maxIncompleteHeight = 0;
46            if (maxAffordableIdx >= 0) {
47                long long cost = 1LL * flowers[maxAffordableIdx] * (maxAffordableIdx + 1) - prefixSum[maxAffordableIdx + 1];
48                long long remaining = newFlowers - cost;
49                maxIncompleteHeight = min((long long)flowers[maxAffordableIdx] + remaining / (maxAffordableIdx + 1), (long long)target - 1);
50            }
51
52            long long currentBeauty = 1LL * numFullGardens * full + maxIncompleteHeight * partial;
53            maxBeauty = max(maxBeauty, currentBeauty);
54        }
55
56        return maxBeauty;
57    }
58};
59

1function maximumBeauty(
2    flowers: number[],
3    newFlowers: number,
4    target: number,
5    full: number,
6    partial: number,
7): number {
8    flowers.sort((a, b) => a - b);
9    const n = flowers.length;
10
11    const prefixSum: number[] = Array(n + 1).fill(0);
12    for (let i = 1; i <= n; i++) {
13        prefixSum[i] = prefixSum[i - 1] + flowers[i - 1];
14    }
15
16    let fullGardenCount = flowers.filter(f => f >= target).length;
17    let maxBeauty = 0;
18
19    for (; fullGardenCount <= n; ++fullGardenCount) {
20        if (fullGardenCount > 0) {
21            const flowersNeeded = Math.max(target - flowers[n - fullGardenCount], 0);
22            newFlowers -= flowersNeeded;
23        }
24
25        if (newFlowers < 0) break;
26
27        // Binary search using first_true_index template (inverted condition)
28        const incompleteCount = n - fullGardenCount;
29        let left = 0;
30        let right = incompleteCount;
31        let firstTrueIndex = incompleteCount;
32
33        while (left <= right) {
34            const mid = Math.floor((left + right) / 2);
35            if (mid >= incompleteCount) {
36                firstTrueIndex = mid;
37                right = mid - 1;
38            } else {
39                const cost = flowers[mid] * (mid + 1) - prefixSum[mid + 1];
40                if (cost > newFlowers) {  // Too expensive
41                    firstTrueIndex = mid;
42                    right = mid - 1;
43                } else {
44                    left = mid + 1;
45                }
46            }
47        }
48
49        const maxAffordableIdx = firstTrueIndex - 1;
50        let minIncompleteFlowers = 0;
51
52        if (maxAffordableIdx >= 0) {
53            const cost = flowers[maxAffordableIdx] * (maxAffordableIdx + 1) - prefixSum[maxAffordableIdx + 1];
54            const remaining = newFlowers - cost;
55            minIncompleteFlowers = Math.min(
56                flowers[maxAffordableIdx] + Math.floor(remaining / (maxAffordableIdx + 1)),
57                target - 1
58            );
59        }
60
61        const currentBeauty = fullGardenCount * full + minIncompleteFlowers * partial;
62        maxBeauty = Math.max(maxBeauty, currentBeauty);
63    }
64
65    return maxBeauty;
66}
67

Solution Approach

First, we sort the flowers array and create a prefix sum array for efficient range sums.

flowers.sort()
n = len(flowers)
prefix_sum = list(accumulate(flowers, initial=0))

For each configuration with x complete gardens, we use the binary search template to find the maximum garden index we can afford to level up.

Inner Binary Search Using first_true_index Template:

We want to find the maximum index where we can afford to raise gardens [0...idx] to flowers[idx] level. This is a "last true" pattern, so we invert:

too_expensive(idx) = cost_to_level(idx) > newFlowers

Pattern: false, false, ..., false, true, true

For small indices: cost is affordable → too_expensive = false
For large indices: cost exceeds budget → too_expensive = true

The maximum affordable index = first_true_index - 1.

Binary Search Template:

left, right = 0, n - num_complete  # Extended right by 1 for edge case
first_true_index = 0  # Default: even index 0 is too expensive

while left <= right:
    mid = (left + right) // 2
    cost = flowers[mid] * (mid + 1) - prefix_sum[mid + 1]
    if cost > newFlowers:  # Too expensive
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

max_affordable_idx = first_true_index - 1

If max_affordable_idx >= 0, we can level gardens [0...max_affordable_idx] and distribute remaining flowers evenly.

Time Complexity: O(n log n) - outer loop O(n) × inner binary search O(log n).

Space Complexity: O(n) for the prefix sum array.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

flowers = [2, 4, 5, 3]
newFlowers = 10
target = 6
full = 20
partial = 5

Step 1: Sort and Setup After sorting: flowers = [2, 3, 4, 5] Prefix sum array: s = [0, 2, 5, 9, 14]

Step 2: Find Initial Complete Gardens Using binary search, we find that garden at index 3 (with 5 flowers) is the only one close to being complete. So initially, i = 1 (we can try having 1 to 4 complete gardens).

Step 3: Enumerate Complete Garden Configurations

Configuration 1: x = 1 complete garden (completing the rightmost garden)

Garden at index 3 needs 6 - 5 = 1 flower to complete
Remaining flowers: 10 - 1 = 9
Incomplete gardens: [2, 3, 4] at indices 0, 1, 2
Binary search to maximize minimum:
- Can we bring all 3 gardens to level 4? Cost = 4 × 3 - (2+3+4) = 12 - 9 = 3 ✓
- After bringing all to level 4, we have 9 - 3 = 6 flowers left
- We can add 6 // 3 = 2 flowers to each, making them all have 6 flowers
- But wait! 6 would make them complete, so cap at target - 1 = 5
Minimum among incomplete: 5
Beauty: 1 × 20 + 5 × 5 = 45

Configuration 2: x = 2 complete gardens

Gardens at indices 2 and 3 need (6-4) + (6-5) = 3 flowers total
Remaining flowers: 10 - 3 = 7
Incomplete gardens: [2, 3] at indices 0, 1
Binary search to maximize minimum:
- Can we bring both to level 3? Cost = 3 × 2 - (2+3) = 6 - 5 = 1 ✓
- After bringing both to level 3, we have 7 - 1 = 6 flowers left
- We can add 6 // 2 = 3 flowers to each, making them both have 6 flowers
- Cap at target - 1 = 5
Minimum among incomplete: 5
Beauty: 2 × 20 + 5 × 5 = 65

Configuration 3: x = 3 complete gardens

Gardens at indices 1, 2, 3 need (6-3) + (6-4) + (6-5) = 6 flowers total
Remaining flowers: 10 - 6 = 4
Incomplete gardens: [2] at index 0
We can add all 4 flowers to this garden: 2 + 4 = 6
But 6 would make it complete, so cap at 5
Minimum among incomplete: 5
Beauty: 3 × 20 + 5 × 5 = 85

Configuration 4: x = 4 complete gardens

All gardens need to be complete
Cost: (6-2) + (6-3) + (6-4) + (6-5) = 4 + 3 + 2 + 1 = 10 flowers
Remaining flowers: 10 - 10 = 0 ✓
No incomplete gardens, so partial beauty = 0
Beauty: 4 × 20 + 0 × 5 = 80

Result: The maximum beauty is 85, achieved by completing 3 gardens and keeping 1 incomplete garden at 5 flowers.

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by:

Initial sorting of the flowers array: O(n log n)
Creating the prefix sum array using accumulate: O(n)
Binary search to find initial value of i: O(log n)
The main loop runs at most n + 1 iterations (from i to n)
Inside each iteration:
- Calculating max(target - flowers[n - x], 0): O(1)
- Binary search loop to find the optimal position: O(log n)
- Other operations are O(1)

Therefore, the overall time complexity is O(n log n) + O(n) × O(log n) = O(n log n).

Space Complexity: O(n)

The space complexity comes from:

The prefix sum array s created by accumulate: O(n)
Other variables (ans, i, l, r, mid, x, y, cost) use constant space: O(1)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template for Inner Search

The inner binary search finds the maximum affordable index (a "last true" pattern). Using the standard template directly fails.

Wrong approach:

while left < right:
    mid = (left + right + 1) >> 1
    if cost <= newFlowers:
        left = mid
    else:
        right = mid - 1

Correct approach (inverted to first_true_index):

first_true_index = incompleteCount  # Default
while left <= right:
    mid = (left + right) // 2
    if cost > newFlowers:  # Too expensive
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
max_affordable_idx = first_true_index - 1

2. Not Handling Empty Incomplete Gardens

When all gardens are complete (num_complete == n), the binary search has no valid range.

Solution: The template handles this naturally - when incompleteCount = 0, first_true_index = 0, so max_affordable_idx = -1, giving partial_level = 0.

3. Integer Overflow in Cost Calculation

The cost flowers[mid] * (mid + 1) can overflow in languages with fixed integer sizes.

Solution: Use appropriate data types:

long cost = (long) flowers[mid] * (mid + 1) - prefixSum[mid + 1];

4. Forgetting to Restore newFlowers

The Java solution modifies newFlowers in-place and must restore it at the end of each iteration for the next configuration to work correctly.

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

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?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know