#2234

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Total Beauty of the Gardens

Determine the maximum total beauty of gardens by strategically planting flowers using binary search over achievable flower counts.

array two pointers binary search greedy sorting

Problem Statement

Alice manages a set of gardens, each with a certain number of flowers, and wants to maximize their total beauty by planting additional flowers. You are given an array flowers where flowers[i] represents the current flowers in garden i, along with integers newFlowers, target, full, and partial. New flowers can be added but existing flowers cannot be removed.

A garden is considered complete if it reaches at least target flowers. The total beauty is computed as full times the number of complete gardens plus partial times the minimum flower count among incomplete gardens. Determine the maximum total beauty Alice can achieve by optimally distributing the new flowers across the gardens.

Examples

Example 1

Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1

Output: 14

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.

Example 2

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

Output: 30

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.

Constraints

1 <= flowers.length <= 105
1 <= flowers[i], target <= 105
1 <= newFlowers <= 1010
1 <= full, partial <= 105

Solution Approach

Sort and Precompute Prefix Sums

Sort the gardens by current flowers to efficiently identify incomplete gardens and precompute prefix sums. This allows quick calculation of how many flowers are needed to raise the smallest gardens toward a candidate minimum during the binary search step.

Binary Search Over Minimum Flower Levels

Use binary search over possible minimum flower counts for incomplete gardens. For each candidate, check if it is feasible given newFlowers, while simultaneously considering the number of complete gardens. This leverages the pattern of binary search over the answer space to prune impossible scenarios efficiently.

Combine Full and Partial Contributions

For each feasible split between complete and incomplete gardens, calculate total beauty as full * complete gardens + partial * minimum of incomplete gardens. Track the maximum value across all configurations to produce the answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by sorting O(n log n) and binary search over flower levels, with O(n) per feasibility check using prefix sums. Space complexity is O(n) for storing sorted gardens and prefix sums.

What Interviewers Usually Probe

Ask how to efficiently decide which gardens to make complete when newFlowers is limited.
Look for recognition that sorting plus prefix sums can quickly compute required flowers for minimum incomplete gardens.
Probe whether candidate minimum levels can be efficiently tested via binary search over the answer space.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the minimum flower count among incomplete gardens when calculating partial beauty.
Trying to brute-force all combinations of flower distributions instead of using binary search over the valid answer space.
Neglecting to handle edge cases where all gardens can become complete or when no additional flowers are available.

Follow-up variants

Maximizing beauty when full and partial values vary dynamically for each garden.
Considering additional constraints where some gardens cannot receive more flowers.
Finding the number of planting ways that achieve the maximum total beauty rather than the value itself.

FAQ

What pattern does Maximum Total Beauty of the Gardens primarily use?

This problem relies on binary search over the valid answer space combined with sorting and prefix sums to efficiently determine feasible minimum flower levels.

How do I decide which gardens to make complete first?

Sort gardens by current flowers and prioritize adding flowers to the smallest incomplete gardens to reach target, while tracking newFlowers usage.

Can all gardens become complete and still maximize beauty?

Not always; sometimes leaving a few gardens below target yields higher total beauty due to the partial contribution formula.

What is the time complexity of this solution?

Sorting is O(n log n) and binary search over flower levels runs in O(log(max(target, flowers))) with O(n) feasibility checks, giving overall O(n log n + n log target).

What is a common mistake when implementing this problem?

A frequent error is ignoring the partial beauty for incomplete gardens or miscalculating the minimum flower count when distributing new flowers.

terminal

Solution

Solution 1: Enumeration + Binary Search

We note that if the number of flowers in a garden is already greater than or equal to $\textit{target}$, then this garden is already a perfect garden and cannot be changed. For imperfect gardens, we can plant more flowers to make them perfect gardens.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def maximumBeauty(
        self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int
    ) -> int:
        flowers.sort()
        n = len(flowers)
        s = list(accumulate(flowers, initial=0))
        ans, i = 0, n - bisect_left(flowers, target)
        for x in range(i, n + 1):
            newFlowers -= 0 if x == 0 else max(target - flowers[n - x], 0)
            if newFlowers < 0:
                break
            l, r = 0, n - x - 1
            while l < r:
                mid = (l + r + 1) >> 1
                if flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers:
                    l = mid
                else:
                    r = mid - 1
            y = 0
            if r != -1:
                cost = flowers[l] * (l + 1) - s[l + 1]
                y = min(flowers[l] + (newFlowers - cost) // (l + 1), target - 1)
            ans = max(ans, x * full + y * partial)
        return ans

Continue Practicing

#2271 maximum white tiles covered by a carpet #2071 maximum number of tasks you can assign #2406 divide intervals into minimum number of groups