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 _themaximum total beauty that Alice can obtain after planting at most _newFlowers flowers.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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^5
  • 1 <= flowers[i], target <= 10^5
  • 1 <= newFlowers <= 1010
  • 1 <= full, partial <= 10^5

Solution

Method 1 – Greedy + Binary Search

Intuition

To maximize total beauty, we want to maximize the number of complete gardens (with at least target flowers) and, for incomplete gardens, maximize the minimum number of flowers among them. By sorting the gardens and using binary search, we can efficiently distribute new flowers to achieve the best result.

Approach

  1. Sort the flowers array.
  2. For each possible number of complete gardens (from 0 to n):
    • Use binary search to find the maximum minimum value for incomplete gardens after distributing remaining flowers.
    • Calculate total beauty as full * complete_gardens + partial * min_incomplete.
    • Track the maximum total beauty.
  3. Return the maximum beauty found.

Complexity

  • ⏰ Time complexity: O(n log n + n log target) — Sorting and binary search for each possible complete garden count.
  • 🧺 Space complexity: O(n) — For sorted array and prefix sums.

Code

 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
26
27
28
29
30
31

class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
        int n = flowers.size();
        sort(flowers.begin(), flowers.end());
        for (int& x : flowers) x = min(x, target);
        vector<long long> pre(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + flowers[i];
        long long ans = 0;
        for (int c = 0; c <= n; ++c) {
            long long rem = newFlowers;
            if (c) rem -= target * c - (pre[n] - pre[n-c]);
            if (rem < 0) continue;
            int l = 0, r = target-1, minInc = 0;
            while (l <= r) {
                int m = (l + r) / 2;
                int idx = upper_bound(flowers.begin(), flowers.end()-c, m) - flowers.begin();
                long long need = 1LL * m * idx - pre[idx];
                if (need <= rem) {
                    minInc = m;
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            long long cur = 1LL * full * c + (c < n ? 1LL * partial * minInc : 0);
            ans = max(ans, cur);
        }
        return ans;
    }
};
 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

func maximumBeauty(flowers []int, newFlowers int64, target, full, partial int) int64 {
    n := len(flowers)
    for i := range flowers {
        if flowers[i] > target {
            flowers[i] = target
        }
    }
    sort.Ints(flowers)
    pre := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + int64(flowers[i])
    }
    ans := int64(0)
    for c := 0; c <= n; c++ {
        rem := newFlowers
        if c > 0 {
            rem -= int64(target*c) - (pre[n] - pre[n-c])
        }
        if rem < 0 {
            continue
        }
        l, r, minInc := 0, target-1, 0
        for l <= r {
            m := (l + r) / 2
            idx := sort.Search(n-c, func(i int) bool { return flowers[i] > m })
            need := int64(m*idx) - pre[idx]
            if need <= rem {
                minInc = m
                l = m + 1
            } else {
                r = m - 1
            }
        }
        cur := int64(full*c)
        if c < n {
            cur += int64(partial * minInc)
        }
        if cur > ans {
            ans = cur
        }
    }
    return ans
}
 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
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.length;
        Arrays.sort(flowers);
        for (int i = 0; i < n; ++i) flowers[i] = Math.min(flowers[i], target);
        long[] pre = new long[n+1];
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + flowers[i];
        long ans = 0;
        for (int c = 0; c <= n; ++c) {
            long rem = newFlowers;
            if (c > 0) rem -= target * c - (pre[n] - pre[n-c]);
            if (rem < 0) continue;
            int l = 0, r = target-1, minInc = 0;
            while (l <= r) {
                int m = (l + r) / 2;
                int idx = upperBound(flowers, 0, n-c, m);
                long need = 1L * m * idx - pre[idx];
                if (need <= rem) {
                    minInc = m;
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            long cur = 1L * full * c + (c < n ? 1L * partial * minInc : 0);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
    private int upperBound(int[] arr, int l, int r, int x) {
        while (l < r) {
            int m = (l + r) / 2;
            if (arr[m] > x) r = m;
            else l = m + 1;
        }
        return l;
    }
}
 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
26
27
28
29
30

class Solution {
    fun maximumBeauty(flowers: IntArray, newFlowers: Long, target: Int, full: Int, partial: Int): Long {
        val n = flowers.size
        for (i in flowers.indices) flowers[i] = minOf(flowers[i], target)
        flowers.sort()
        val pre = LongArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + flowers[i]
        var ans = 0L
        for (c in 0..n) {
            var rem = newFlowers
            if (c > 0) rem -= target.toLong() * c - (pre[n] - pre[n-c])
            if (rem < 0) continue
            var l = 0; var r = target-1; var minInc = 0
            while (l <= r) {
                val m = (l + r) / 2
                val idx = flowers.slice(0 until n-c).indexOfFirst { it > m }.let { if (it == -1) n-c else it }
                val need = m.toLong() * idx - pre[idx]
                if (need <= rem) {
                    minInc = m
                    l = m + 1
                } else {
                    r = m - 1
                }
            }
            val cur = full.toLong() * c + if (c < n) partial.toLong() * minInc else 0L
            ans = maxOf(ans, cur)
        }
        return ans
    }
}
 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
26
27

def maximum_beauty(flowers: list[int], new_flowers: int, target: int, full: int, partial: int) -> int:
    n = len(flowers)
    flowers = [min(x, target) for x in flowers]
    flowers.sort()
    pre = [0] * (n+1)
    for i in range(n):
        pre[i+1] = pre[i] + flowers[i]
    ans = 0
    for c in range(n+1):
        rem = new_flowers
        if c:
            rem -= target * c - (pre[n] - pre[n-c])
        if rem < 0:
            continue
        l, r, min_inc = 0, target-1, 0
        while l <= r:
            m = (l + r) // 2
            idx = next((i for i, x in enumerate(flowers[:n-c]) if x > m), n-c)
            need = m * idx - pre[idx]
            if need <= rem:
                min_inc = m
                l = m + 1
            else:
                r = m - 1
        cur = full * c + (partial * min_inc if c < n else 0)
        ans = max(ans, cur)
    return ans
 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
26
27
28
29
30
31
32

impl Solution {
    pub fn maximum_beauty(flowers: Vec<i32>, new_flowers: i64, target: i32, full: i32, partial: i32) -> i64 {
        let n = flowers.len();
        let mut flowers: Vec<i32> = flowers.into_iter().map(|x| x.min(target)).collect();
        flowers.sort();
        let mut pre = vec![0i64; n+1];
        for i in 0..n { pre[i+1] = pre[i] + flowers[i] as i64; }
        let mut ans = 0i64;
        for c in 0..=n {
            let mut rem = new_flowers;
            if c > 0 {
                rem -= target as i64 * c as i64 - (pre[n] - pre[n-c]);
            }
            if rem < 0 { continue; }
            let (mut l, mut r, mut min_inc) = (0, target-1, 0);
            while l <= r {
                let m = (l + r) / 2;
                let idx = flowers[..n-c].iter().position(|&x| x > m).unwrap_or(n-c);
                let need = m as i64 * idx as i64 - pre[idx];
                if need <= rem {
                    min_inc = m;
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            let cur = full as i64 * c as i64 + if c < n { partial as i64 * min_inc as i64 } else { 0 };
            ans = ans.max(cur);
        }
        ans
    }
}
 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
26
27
28
29
30

class Solution {
    maximumBeauty(flowers: number[], newFlowers: number, target: number, full: number, partial: number): number {
        const n = flowers.length;
        flowers = flowers.map(x => Math.min(x, target)).sort((a, b) => a - b);
        const pre = Array(n+1).fill(0);
        for (let i = 0; i < n; ++i) pre[i+1] = pre[i] + flowers[i];
        let ans = 0;
        for (let c = 0; c <= n; ++c) {
            let rem = newFlowers;
            if (c) rem -= target * c - (pre[n] - pre[n-c]);
            if (rem < 0) continue;
            let l = 0, r = target-1, minInc = 0;
            while (l <= r) {
                const m = Math.floor((l + r) / 2);
                let idx = 0;
                while (idx < n-c && flowers[idx] <= m) ++idx;
                const need = m * idx - pre[idx];
                if (need <= rem) {
                    minInc = m;
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            const cur = full * c + (c < n ? partial * minInc : 0);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}