# Maximum Total Beauty of the Gardens
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-total-beauty-of-the-gardens)
Canonical: https://scaleengineer.com/dsa/problems/maximum-total-beauty-of-the-gardens
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit)
---
## Problem
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.

**Example 2:**

**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.

**Constraints:**

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

# Approaches
## Iterative Approach with Nested Loop
This approach systematically explores all possibilities by breaking down the problem. We first sort the `flowers` array to make optimal choices easily. The main idea is to iterate through every possible number of gardens we can make 'complete', from `n` down to `0`. For each number of complete gardens, `k`, we calculate the minimum cost required by picking the `k` gardens that are already closest to the `target`. If we can afford this cost with our `newFlowers`, we use the remaining flowers to improve the 'partial' beauty component.

The partial beauty is determined by the minimum number of flowers in any incomplete garden. To maximize this minimum, we can level up a prefix of the sorted incomplete gardens. We iterate through all possible prefixes, calculate the maximum level they can be uniformly raised to with the remaining flowers, and find the best possible partial beauty. This process is repeated for each `k`, and we keep track of the maximum total beauty seen.
**Time:** O(n^2) due to the nested loops. The outer loop runs `n` times, and the inner loop can run up to `n` times. Sorting takes an initial `O(n log n)`. · **Space:** O(n) to store the sorted array and prefix sums.
**Pros:** The logic is straightforward to understand.; It correctly explores the trade-off between making more gardens complete versus raising the minimum level of incomplete ones.
**Cons:** The nested loop structure leads to a quadratic time complexity, which is too slow for the given constraints.
### Explanation
The algorithm begins by sorting the `flowers` array. This allows us to greedily decide which gardens to complete and which to level up. To make `k` gardens complete, it's always optimal to pick the `k` gardens that already have the most flowers, i.e., the last `k` gardens in the sorted array. To maximize the minimum of the incomplete gardens, it's best to raise the gardens with the fewest flowers, i.e., a prefix of the sorted array.

We loop through `k` from `n` down to `0`, representing the number of gardens we will make complete. In each iteration, we calculate the cost. If we have enough `newFlowers`, we find the remaining flowers and then try to find the best partial score. The partial score is maximized by finding the highest possible minimum `L` among the `n-k` incomplete gardens. This is done via a second, nested loop that checks every possible prefix `0...j` of the incomplete gardens and calculates the maximum level `L` it can be raised to. The total beauty is then calculated and compared with the global maximum.

```java
import java.util.Arrays;

class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.length;
        long[] sortedFlowers = new long[n];
        for (int i = 0; i < n; i++) {
            sortedFlowers[i] = Math.min(flowers[i], target);
        }
        Arrays.sort(sortedFlowers);

        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + sortedFlowers[i];
        }

        long maxBeauty = 0;

        // Case with 0 complete gardens
        long maxLevel = 0;
        for (int j = 0; j < n; j++) {
            long cost = (j + 1) * sortedFlowers[j] - prefixSum[j + 1];
            if (cost <= newFlowers) {
                long currentLevel = (newFlowers - cost) / (j + 1) + sortedFlowers[j];
                maxLevel = Math.max(maxLevel, currentLevel);
            }
        }
        if (n > 0) {
             maxBeauty = Math.max(maxBeauty, Math.min(maxLevel, target - 1) * partial);
        }
       

        long costToComplete = 0;
        for (int i = n - 1; i >= 0; i--) {
            costToComplete += Math.max(0, target - sortedFlowers[i]);
            if (costToComplete > newFlowers) {
                break;
            }

            long remainingFlowers = newFlowers - costToComplete;
            int numComplete = n - i;
            int numIncomplete = i;

            maxLevel = 0;
            if (numIncomplete > 0) {
                // Find max level for incomplete gardens 0 to i-1
                int low = 0, high = numIncomplete - 1, bestJ = -1;
                while(low <= high) {
                    int mid = low + (high - low) / 2;
                    if (sortedFlowers[mid] * (mid + 1) - prefixSum[mid + 1] <= remainingFlowers) {
                        bestJ = mid;
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
                if (bestJ != -1) {
                    long cost = (bestJ + 1) * sortedFlowers[bestJ] - prefixSum[bestJ + 1];
                    maxLevel = (remainingFlowers - cost) / (bestJ + 1) + sortedFlowers[bestJ];
                }
            }
            
            long currentBeauty = (long) numComplete * full;
            if (numIncomplete > 0) {
                currentBeauty += Math.min(maxLevel, target - 1) * partial;
            }
            maxBeauty = Math.max(maxBeauty, currentBeauty);
        }
        
        if (costToComplete <= newFlowers) {
             maxBeauty = Math.max(maxBeauty, (long)n * full);
        }

        return maxBeauty;
    }
}
```
*Note: The provided code snippet is a slightly optimized O(N log N) version of the O(N^2) idea, using binary search to find the best prefix `j` instead of a linear scan. A pure O(N^2) implementation would be too slow.*
### Algorithm
*   Sort the `flowers` array in non-decreasing order. This helps in optimally choosing which gardens to make complete (the ones already having more flowers) and which ones to level up (the ones with fewer flowers).
*   Calculate the prefix sums of the sorted `flowers` array. This will allow `O(1)` calculation of the sum of flowers in any subarray. Use `long` data type to prevent overflow.
*   Iterate through the number of gardens to make complete, let's say `k`, from `n` down to `0`.
*   For each `k`:
    *   Calculate the cost to make the `k` gardens with the most flowers complete. These are `flowers[n-k], ..., flowers[n-1]`. The cost is `k * target - sum(flowers[n-k...n-1])`.
    *   If this cost exceeds `newFlowers`, we cannot make `k` (or more) gardens complete, so we can stop iterating.
    *   Otherwise, calculate the remaining flowers: `rem_flowers = newFlowers - cost`.
    *   Now, consider the `n-k` incomplete gardens: `flowers[0], ..., flowers[n-k-1]`. We want to use `rem_flowers` to maximize their minimum level.
    *   Iterate through all possible prefixes of these incomplete gardens, from `j=0` to `n-k-1`. For each prefix `flowers[0...j]`, calculate the maximum level `L` they can all be raised to. This level is `L = (rem_flowers + sum(flowers[0...j])) / (j+1)`.
    *   Keep track of the maximum `L` found among all prefixes for the current `k`. Let this be `max_L`. Note that `max_L` cannot exceed `target - 1` if `k > 0`.
    *   The total beauty for this `k` is `k * full + max_L * partial`.
    *   Update the overall maximum beauty found so far.
*   Handle the edge case where all `n` gardens can be made complete. If so, the beauty is `n * full`.

## Greedy with Binary Search / Two Pointers
This approach significantly improves upon the previous one by optimizing the search for the best partial beauty component. The overall structure remains the same: sort the flowers and iterate through the number of gardens, `k`, to make complete. However, for each `k`, instead of a linear scan to find the best minimum level `L` for the incomplete gardens, we use binary search.

The key insight is that the feasibility of achieving a certain minimum level `L` is a monotonic function. If we have enough flowers to ensure all incomplete gardens have at least `L` flowers, we certainly have enough to ensure they all have `L-1` flowers. This allows us to binary search for the maximum possible `L` in the range `[0, target-1]`.

To check if a given level `L` is achievable within our remaining flower budget, we need to calculate the cost. This involves finding all incomplete gardens with fewer than `L` flowers and summing up the flowers needed to raise them to `L`. This sub-problem can also be solved efficiently using another binary search (`upper_bound`) on the sorted array of incomplete gardens to find the boundary. This nested binary search structure leads to a much better time complexity.
**Time:** O(n log n + n * log(target) * log n). Sorting takes `O(n log n)`. The main loop runs `n` times. Inside, a binary search takes `O(log target)` steps, and each step takes `O(log n)` for the inner search. The two-pointer optimization shown in the code reduces this to O(n log n). · **Space:** O(n) for storing the sorted array and prefix sums.
**Pros:** Much more efficient and will pass within the time limits for the given constraints.; It's a standard and powerful technique for problems involving searching for an optimal value with a monotonic property.
**Cons:** The logic is more complex, involving a nested binary search structure.; Implementation requires careful handling of indices and `long` data types to avoid bugs and overflow.
### Explanation
After sorting `flowers` and calculating prefix sums, we iterate `i` from `n-1` down to `0`, where `i` is the index of the first garden we consider making complete. This means we are trying to make `n-i` gardens complete.

For each `i`, we calculate `costToComplete`. If it's within our `newFlowers` budget, we proceed. We are left with `remainingFlowers` and `i` incomplete gardens (`flowers[0...i-1]`).

Now, we must find the maximum possible value for the minimum flowers in these `i` gardens. We binary search for this value, `L`, in the range `[0, target-1]`. For a given `L` (our `mid` in the binary search), we check if it's possible to make all gardens in `flowers[0...i-1]` have at least `L` flowers. To do this, we find the rightmost garden `p` in this range with `flowers[p] < L`. This is done via a `lower_bound` or `upper_bound` search, which is another binary search. The cost to raise all gardens up to `p` to level `L` is `(p+1)*L - prefixSum[p+1]`. If this cost is not more than `remainingFlowers`, then `L` is achievable, and we try for a higher `L`. Otherwise, `L` is too high.

Once the optimal `L` is found for the current number of complete gardens, we calculate the total beauty and update our overall maximum. This process efficiently finds the optimal balance between complete and incomplete gardens.

```java
import java.util.Arrays;

class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.length;
        long[] sortedFlowers = new long[n];
        for (int i = 0; i < n; i++) {
            sortedFlowers[i] = flowers[i];
        }
        Arrays.sort(sortedFlowers);

        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + sortedFlowers[i];
        }

        long maxBeauty = 0;
        long costToComplete = 0;

        int j = n - 1;
        for (int i = n; i >= 0; i--) {
            long remainingFlowers;
            if (i < n) {
                costToComplete += Math.max(0, target - sortedFlowers[i]);
            }
            if (costToComplete > newFlowers) {
                break;
            }
            remainingFlowers = newFlowers - costToComplete;
            
            j = Math.min(j, i - 1);
            while (j >= 0 && (sortedFlowers[j] * (j + 1) - prefixSum[j + 1]) > remainingFlowers) {
                j--;
            }

            long currentBeauty = (long)(n - i) * full;
            if (j >= 0) {
                long level = Math.min(target - 1, sortedFlowers[j] + (remainingFlowers - (sortedFlowers[j] * (j + 1) - prefixSum[j + 1])) / (j + 1));
                currentBeauty += level * partial;
            }
            
            maxBeauty = Math.max(maxBeauty, currentBeauty);
        }

        return maxBeauty;
    }
}
```
*Note: The provided code snippet is a further optimized O(N log N) solution using a two-pointer approach, which is more efficient than the described nested binary search. The pointer `j` for the incomplete gardens does not need to be reset in each iteration of the main loop, as the `remainingFlowers` budget is non-decreasing.*
### Algorithm
*   Sort the `flowers` array and compute prefix sums, similar to the previous approach. Use `long` for sums and costs to avoid overflow. It's beneficial to cap flower counts at `target` since any excess is wasted.
*   Initialize `max_beauty`. A good starting point is to calculate the beauty for the case of 0 complete gardens. This involves finding the max level `L` achievable using all `newFlowers` on all `n` gardens. This `L` can be found using binary search.
*   Iterate through the number of gardens to make complete, `k`, from `n` down to `1`.
*   For each `k`:
    *   Calculate the cost to make the `k` largest gardens complete: `cost_k = k * target - sum(flowers[n-k...n-1])`.
    *   If `cost_k > newFlowers`, we cannot afford it, so break the loop.
    *   Calculate `rem_flowers = newFlowers - cost_k`.
    *   The `n-k` gardens `flowers[0...n-k-1]` are incomplete. We need to find the maximum possible minimum level `L` for this group using `rem_flowers`.
    *   This subproblem has a monotonic property: if level `L` is achievable, any level `L' < L` is also achievable. This allows for binary search on the answer `L`.
    *   Perform a binary search for `L` in the range `[0, target-1]`.
    *   The `check(L)` function for this binary search determines if `min_level = L` is possible. To do this:
        *   Find the rightmost garden `p` among the incomplete ones such that `flowers[p] < L`. This can be done efficiently with another binary search (`upper_bound`) on `flowers[0...n-k-1]`.
        *   The cost to raise all gardens `0...p` to level `L` is `(p+1) * L - sum(flowers[0...p])`.
        *   If this cost is `<= rem_flowers`, `check(L)` returns true.
    *   The result of the binary search is the maximum `L` for the current `k`. Let it be `max_L`.
    *   Calculate beauty `k * full + max_L * partial` and update `max_beauty`.
*   Finally, consider the case where all `n` gardens are made complete, which gives a beauty of `n * full` if affordable, and update `max_beauty` one last time.

# Solutions
### Java

```java
class Solution {
public
  long maximumBeauty(int[] flowers, long newFlowers, int target, int full,
                     int partial) {
    Arrays.sort(flowers);
    int n = flowers.length;
    long[] s = new long[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + flowers[i];
    }
    long ans = 0;
    int x = 0;
    for (int v : flowers) {
      if (v >= target) {
        ++x;
      }
    }
    for (; x <= n; ++x) {
      newFlowers -= (x == 0 ? 0 : Math.max(target - flowers[n - x], 0));
      if (newFlowers < 0) {
        break;
      }
      int l = 0, r = n - x - 1;
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if ((long)flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      long y = 0;
      if (r != -1) {
        long cost = (long)flowers[l] * (l + 1) - s[l + 1];
        y = Math.min(flowers[l] + (newFlowers - cost) / (l + 1), target - 1);
      }
      ans = Math.max(ans, (long)x * full + y * partial);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumBeauty(vector<int> &flowers, long long newFlowers,
                          int target, int full, int partial) {
    sort(flowers.begin(), flowers.end());
    int n = flowers.size();
    long long s[n + 1];
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + flowers[i - 1];
    }
    long long ans = 0;
    int i = flowers.end() - lower_bound(flowers.begin(), flowers.end(), target);
    for (int x = i; x <= n; ++x) {
      newFlowers -= (x == 0 ? 0 : max(target - flowers[n - x], 0));
      if (newFlowers < 0) {
        break;
      }
      int l = 0, r = n - x - 1;
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (1LL * flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      int y = 0;
      if (r != -1) {
        long long cost = 1LL * flowers[l] * (l + 1) - s[l + 1];
        long long mx = flowers[l] + (newFlowers - cost) / (l + 1);
        long long threshold = target - 1;
        y = min(mx, threshold);
      }
      ans = max(ans, 1LL * x * full + 1LL * y * partial);
    }
    return ans;
  }
};

```

### Python

```python
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

```