Maximum Total Beauty of the Gardens

Hard

#2035Time: 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.1 company

Patterns

Two Pointers Greedy Enumeration Prefix Sum

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Intuit

Prompt

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 i^th 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 <= 10⁵
1 <= flowers[i], target <= 10⁵
1 <= newFlowers <= 10¹⁰
1 <= full, partial <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {5        int n = flowers.length;6        long[] sortedFlowers = new long[n];7        for (int i = 0; i < n; i++) {8            sortedFlowers[i] = Math.min(flowers[i], target);9        }10        Arrays.sort(sortedFlowers);11 12        long[] prefixSum = new long[n + 1];13        for (int i = 0; i < n; i++) {14            prefixSum[i + 1] = prefixSum[i] + sortedFlowers[i];15        }16 17        long maxBeauty = 0;18 19        // Case with 0 complete gardens20        long maxLevel = 0;21        for (int j = 0; j < n; j++) {22            long cost = (j + 1) * sortedFlowers[j] - prefixSum[j + 1];23            if (cost <= newFlowers) {24                long currentLevel = (newFlowers - cost) / (j + 1) + sortedFlowers[j];25                maxLevel = Math.max(maxLevel, currentLevel);26            }27        }28        if (n > 0) {29             maxBeauty = Math.max(maxBeauty, Math.min(maxLevel, target - 1) * partial);30        }31       32 33        long costToComplete = 0;34        for (int i = n - 1; i >= 0; i--) {35            costToComplete += Math.max(0, target - sortedFlowers[i]);36            if (costToComplete > newFlowers) {37                break;38            }39 40            long remainingFlowers = newFlowers - costToComplete;41            int numComplete = n - i;42            int numIncomplete = i;43 44            maxLevel = 0;45            if (numIncomplete > 0) {46                // Find max level for incomplete gardens 0 to i-147                int low = 0, high = numIncomplete - 1, bestJ = -1;48                while(low <= high) {49                    int mid = low + (high - low) / 2;50                    if (sortedFlowers[mid] * (mid + 1) - prefixSum[mid + 1] <= remainingFlowers) {51                        bestJ = mid;52                        low = mid + 1;53                    } else {54                        high = mid - 1;55                    }56                }57                if (bestJ != -1) {58                    long cost = (bestJ + 1) * sortedFlowers[bestJ] - prefixSum[bestJ + 1];59                    maxLevel = (remainingFlowers - cost) / (bestJ + 1) + sortedFlowers[bestJ];60                }61            }62            63            long currentBeauty = (long) numComplete * full;64            if (numIncomplete > 0) {65                currentBeauty += Math.min(maxLevel, target - 1) * partial;66            }67            maxBeauty = Math.max(maxBeauty, currentBeauty);68        }69        70        if (costToComplete <= newFlowers) {71             maxBeauty = Math.max(maxBeauty, (long)n * full);72        }73 74        return maxBeauty;75    }76}

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.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {5        int n = flowers.length;6        long[] sortedFlowers = new long[n];7        for (int i = 0; i < n; i++) {8            sortedFlowers[i] = flowers[i];9        }10        Arrays.sort(sortedFlowers);11 12        long[] prefixSum = new long[n + 1];13        for (int i = 0; i < n; i++) {14            prefixSum[i + 1] = prefixSum[i] + sortedFlowers[i];15        }16 17        long maxBeauty = 0;18        long costToComplete = 0;19 20        int j = n - 1;21        for (int i = n; i >= 0; i--) {22            long remainingFlowers;23            if (i < n) {24                costToComplete += Math.max(0, target - sortedFlowers[i]);25            }26            if (costToComplete > newFlowers) {27                break;28            }29            remainingFlowers = newFlowers - costToComplete;30            31            j = Math.min(j, i - 1);32            while (j >= 0 && (sortedFlowers[j] * (j + 1) - prefixSum[j + 1]) > remainingFlowers) {33                j--;34            }35 36            long currentBeauty = (long)(n - i) * full;37            if (j >= 0) {38                long level = Math.min(target - 1, sortedFlowers[j] + (remainingFlowers - (sortedFlowers[j] * (j + 1) - prefixSum[j + 1])) / (j + 1));39                currentBeauty += level * partial;40            }41            42            maxBeauty = Math.max(maxBeauty, currentBeauty);43        }44 45        return maxBeauty;46    }47}

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.

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  long maximumBeauty(int[] flowers, long newFlowers, int target, int full,4                     int partial) {5    Arrays.sort(flowers);6    int n = flowers.length;7    long[] s = new long[n + 1];8    for (int i = 0; i < n; ++i) {9      s[i + 1] = s[i] + flowers[i];10    }11    long ans = 0;12    int x = 0;13    for (int v : flowers) {14      if (v >= target) {15        ++x;16      }17    }18    for (; x <= n; ++x) {19      newFlowers -= (x == 0 ? 0 : Math.max(target - flowers[n - x], 0));20      if (newFlowers < 0) {21        break;22      }23      int l = 0, r = n - x - 1;24      while (l < r) {25        int mid = (l + r + 1) >> 1;26        if ((long)flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers) {27          l = mid;28        } else {29          r = mid - 1;30        }31      }32      long y = 0;33      if (r != -1) {34        long cost = (long)flowers[l] * (l + 1) - s[l + 1];35        y = Math.min(flowers[l] + (newFlowers - cost) / (l + 1), target - 1);36      }37      ans = Math.max(ans, (long)x * full + y * partial);38    }39    return ans;40  }41}

1class Solution {2public:3  long long maximumBeauty(vector<int> &flowers, long long newFlowers,4                          int target, int full, int partial) {5    sort(flowers.begin(), flowers.end());6    int n = flowers.size();7    long long s[n + 1];8    s[0] = 0;9    for (int i = 1; i <= n; ++i) {10      s[i] = s[i - 1] + flowers[i - 1];11    }12    long long ans = 0;13    int i = flowers.end() - lower_bound(flowers.begin(), flowers.end(), target);14    for (int x = i; x <= n; ++x) {15      newFlowers -= (x == 0 ? 0 : max(target - flowers[n - x], 0));16      if (newFlowers < 0) {17        break;18      }19      int l = 0, r = n - x - 1;20      while (l < r) {21        int mid = (l + r + 1) >> 1;22        if (1LL * flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers) {23          l = mid;24        } else {25          r = mid - 1;26        }27      }28      int y = 0;29      if (r != -1) {30        long long cost = 1LL * flowers[l] * (l + 1) - s[l + 1];31        long long mx = flowers[l] + (newFlowers - cost) / (l + 1);32        long long threshold = target - 1;33        y = min(mx, threshold);34      }35      ans = max(ans, 1LL * x * full + 1LL * y * partial);36    }37    return ans;38  }39};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem