Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1788. Maximize the Beauty of the Garden - Leetcode Solution

Code Implementation

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:
        n = len(flowers)
        flowers = [min(f, target) for f in flowers]
        flowers.sort()
        full_cnt = 0
        while flowers and flowers[-1] == target:
            flowers.pop()
            full_cnt += 1
        n = len(flowers)
        pre_sum = [0]
        for f in flowers:
            pre_sum.append(pre_sum[-1] + f)
        res = 0
        for k in range(full_cnt, full_cnt + n + 1):
            if k == full_cnt + n:
                res = max(res, (k) * full)
                break
            need = (target - flowers[-1]) * (n - (k - full_cnt)) - (pre_sum[-1] - pre_sum[(k - full_cnt)])
            if need > newFlowers:
                continue
            left = 0
            right = target - 1
            while left < right:
                mid = (left + right + 1) // 2
                idx = bisect.bisect_left(flowers, mid, 0, n - (k - full_cnt))
                cost = mid * idx - pre_sum[idx]
                if cost <= newFlowers - need:
                    left = mid
                else:
                    right = mid - 1
            res = max(res, k * full + left * partial)
        return res
      
class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
        int n = flowers.size();
        for (int &f : flowers) f = min(f, target);
        sort(flowers.begin(), flowers.end());
        int full_cnt = 0;
        while (!flowers.empty() && flowers.back() == target) {
            flowers.pop_back();
            full_cnt++;
        }
        n = flowers.size();
        vector<long long> pre_sum(n + 1, 0);
        for (int i = 0; i < n; ++i)
            pre_sum[i + 1] = pre_sum[i] + flowers[i];
        long long res = 0;
        for (int k = full_cnt; k <= full_cnt + n; ++k) {
            if (k == full_cnt + n) {
                res = max(res, 1LL * k * full);
                break;
            }
            long long need = 1LL * (target - flowers[n - (k - full_cnt) - 1]) * (n - (k - full_cnt)) - (pre_sum[n] - pre_sum[k - full_cnt]);
            if (need > newFlowers) continue;
            int left = 0, right = target - 1;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                int idx = lower_bound(flowers.begin(), flowers.begin() + n - (k - full_cnt), mid) - flowers.begin();
                long long cost = 1LL * mid * idx - pre_sum[idx];
                if (cost <= newFlowers - need) left = mid;
                else right = mid - 1;
            }
            res = max(res, 1LL * k * full + 1LL * left * partial);
        }
        return res;
    }
};
      
class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.length;
        for (int i = 0; i < n; ++i)
            flowers[i] = Math.min(flowers[i], target);
        Arrays.sort(flowers);
        int fullCnt = 0;
        while (n > 0 && flowers[n - 1] == target) {
            n--;
            fullCnt++;
        }
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; ++i)
            preSum[i + 1] = preSum[i] + flowers[i];
        long res = 0;
        for (int k = fullCnt; k <= fullCnt + n; ++k) {
            if (k == fullCnt + n) {
                res = Math.max(res, 1L * k * full);
                break;
            }
            long need = 1L * (target - flowers[n - (k - fullCnt) - 1]) * (n - (k - fullCnt)) - (preSum[n] - preSum[k - fullCnt]);
            if (need > newFlowers) continue;
            int left = 0, right = target - 1;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                int idx = Arrays.binarySearch(flowers, 0, n - (k - fullCnt), mid);
                if (idx < 0) idx = -idx - 1;
                long cost = 1L * mid * idx - preSum[idx];
                if (cost <= newFlowers - need) left = mid;
                else right = mid - 1;
            }
            res = Math.max(res, 1L * k * full + 1L * left * partial);
        }
        return res;
    }
}
      
var maximumBeauty = function(flowers, newFlowers, target, full, partial) {
    flowers = flowers.map(f => Math.min(f, target)).sort((a, b) => a - b);
    let fullCnt = 0;
    while (flowers.length > 0 && flowers[flowers.length - 1] === target) {
        flowers.pop();
        fullCnt++;
    }
    let n = flowers.length;
    let preSum = [0];
    for (let f of flowers) preSum.push(preSum[preSum.length - 1] + f);
    let res = 0;
    for (let k = fullCnt; k <= fullCnt + n; ++k) {
        if (k === fullCnt + n) {
            res = Math.max(res, k * full);
            break;
        }
        let need = (target - flowers[flowers.length - (k - fullCnt) - 1]) * (n - (k - fullCnt)) -
            (preSum[preSum.length - 1] - preSum[k - fullCnt]);
        if (need > newFlowers) continue;
        let left = 0, right = target - 1;
        while (left < right) {
            let mid = Math.floor((left + right + 1) / 2);
            let idx = lowerBound(flowers, mid, 0, n - (k - fullCnt));
            let cost = mid * idx - preSum[idx];
            if (cost <= newFlowers - need) left = mid;
            else right = mid - 1;
        }
        res = Math.max(res, k * full + left * partial);
    }
    return res;

    function lowerBound(arr, target, start, end) {
        let l = start, r = end;
        while (l < r) {
            let m = Math.floor((l + r) / 2);
            if (arr[m] < target) l = m + 1;
            else r = m;
        }
        return l;
    }
};

Problem Description

You are given an array flowers where flowers[i] represents the number of flowers in the i-th garden. You also have newFlowers new flowers you can plant across these gardens. Your goal is to maximize the overall "beauty" of the gardens. The beauty is calculated as follows:
  • For each garden that has at least target flowers, it is considered "full" and contributes full points to the total beauty.
  • For the remaining gardens (not full), the beauty is increased by partial times the minimum number of flowers among these gardens.
  • You can distribute newFlowers however you like, but cannot exceed target flowers in any garden.
The task is to determine the maximum possible beauty you can achieve by optimally distributing the new flowers. Constraints:
  • Each garden can be filled up to but not above target flowers.
  • Each flower can be used only once.
  • There is only one valid solution for the maximum beauty.

Thought Process

At first glance, the problem appears to require trying all possible ways to distribute the newFlowers among the gardens, which would be extremely inefficient. A brute-force solution would involve distributing flowers in all possible combinations, but this would not scale for large inputs. Instead, we notice that:
  • Making a garden "full" (reaching target flowers) is always beneficial because it gives a fixed, high reward (full points).
  • For the remaining gardens, increasing the minimum number of flowers increases the "partial" reward linearly.
  • Thus, the problem reduces to: for each possible number of "full" gardens, maximize the minimum in the rest, while not exceeding the available new flowers.
This insight allows us to shift from brute-force to an efficient approach by sorting, prefix sums, and binary search.

Solution Approach

The solution is built step-by-step as follows:
  1. Cap Each Garden: First, we cap each garden's flower count at target, since adding more does not increase beauty.
  2. Sort the Gardens: Sorting the flower counts allows us to efficiently consider which gardens to fill up to the target.
  3. Count Already Full Gardens: Count how many gardens are already at target. These are already "full".
  4. Prefix Sums: Compute prefix sums of the sorted flower counts, so we can efficiently calculate how much it costs to raise the minimum in a prefix of gardens.
  5. Iterate Over Possible Full Gardens: For each possible number of gardens to make "full" (from the current count up to all gardens), calculate:
    • How many new flowers are needed to make that many gardens full.
    • How many are left to distribute among the remaining gardens.
    • What's the highest minimum for the remaining gardens we can achieve with the leftover flowers (using binary search and prefix sums).
  6. Calculate Beauty: For each split, calculate the total beauty: (full points for each full garden) + (partial times the minimum in the rest, if any).
  7. Track the Maximum: Keep track of the maximum beauty found across all possible splits.
The use of sorting and prefix sums allows us to answer "how much does it cost to raise the minimum to X" in O(1) time, and binary search lets us efficiently find the best minimum.

Example Walkthrough

Let's consider an example:
  • flowers = [1, 3, 1]
  • newFlowers = 7
  • target = 6
  • full = 12
  • partial = 1
Step-by-step:
  1. After capping, flowers = [1, 3, 1] (all below target).
  2. Sort: [1, 1, 3].
  3. None are full yet, so full_cnt = 0.
  4. Suppose we make 2 gardens full:
    • To make the two largest gardens full, need to bring both to 6: (6-3) + (6-1) = 3 + 5 = 8 flowers, but we only have 7.
    • So, try making one garden full: (6-3) = 3 flowers needed. After making one full, 7-3=4 flowers left.
    • Distribute the 4 flowers among the two remaining gardens (both at 1): bring both to 1+2=3, use 4 flowers in total.
    • Minimum among remaining gardens is now 3.
    • Total beauty = 12 (for one full) + 3*1 (partial) = 15.
  5. Try making all 0 gardens full: use 7 flowers to raise the minimum as high as possible. Both 1s can be brought to 4 (using 3+3=6), and 3 remains at 3. Minimum is 3.
  6. Try making all 3 gardens full: need (6-1)+(6-1)+(6-3)=5+5+3=13 flowers, not enough.
  7. The optimal is to make one garden full and raise the rest to 3, for a total beauty of 15.

Time and Space Complexity

Brute-force approach: Would try all possible distributions of newFlowers among gardens, which is exponential and infeasible for large inputs. Optimized approach:
  • Sorting the gardens: O(n log n)
  • Prefix sum computation: O(n)
  • Main loop: For each possible number of full gardens (at most n), we do a binary search (O(log target)) to find the best minimum among the rest.
  • Total: O(n log n + n log target)
  • Space: O(n) for the prefix sum array.
This is efficient and suitable for large inputs.

Summary

The key to solving the "Maximize the Beauty of the Garden" problem is realizing that you can separate the gardens into "full" and "partial" groups, and optimize the distribution of new flowers between these groups. By sorting the gardens, using prefix sums, and applying binary search, we efficiently determine the optimal way to maximize the beauty score. The approach is both elegant and powerful, transforming a seemingly complex problem into a tractable one with smart algorithmic tools.