Maximum total beauty of the gardens

Array Two Pointers Binary Search Greedy Sorting Enumeration Prefix Sum

30.3% acceptance

Feb 25, 2026

451

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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<i64> = flowers.iter().map(|&f| (f as i64).min(target as i64)).collect();
    flowers.sort();
    let target = target as i64;
    let full = full as i64;
    let partial = partial as i64;
    // gardens already at target are always complete; only iterate over workable ones
    let workable = flowers.partition_point(|&f| f < target);
    let base_complete = (n - workable) as i64;

    let mut prefix = vec![0i64; n + 1];
    for i in 0..n { prefix[i + 1] = prefix[i] + flowers[i]; }

    let mut ans = 0i64;
    // j: number of workable gardens we choose to complete (the last j of the workable range)
    // m = workable - j: number of incomplete gardens (first m of workable range)
    for j in 0..=workable {
      let m = workable - j;
      let sum_last_j = prefix[workable] - prefix[m];
      let cost = (j as i64) * target - sum_last_j;
      if cost > new_flowers { break; }
      let rem = new_flowers - cost;
      if m == 0 {
        ans = ans.max((base_complete + j as i64) * full);
      } else {
        // Binary search: find max v such that cost to raise all 0..m to v <= rem
        // constraint: v < target (incomplete gardens)
        let mut lo = 0i64;
        let mut hi = (target - 1).min(flowers[0] + rem);
        while lo < hi {
          let mid = (lo + hi + 1) / 2;
          let lb = flowers[..m].partition_point(|&f| f < mid);
          let need = mid * (lb as i64) - prefix[lb];
          if need <= rem { lo = mid; } else { hi = mid - 1; }
        }
        ans = ans.max((base_complete + j as i64) * full + lo * partial);
      }
    }
    ans
  }
}