Maximum number of groups with increasing length

Array Math Binary Search Greedy Sorting

23.0% acceptance

Feb 25, 2026

421

You are given a 0-indexed array usageLimits of length n. Your task is to create groups using numbers from 0 to n - 1, ensuring that each number, i, is used no more than usageLimits[i] times in total across all groups. You must also satisfy the following conditions: Each group must consist of distinct numbers, meaning that no duplicate numbers are allowed within a single group. Each group (except the first one) must have a length strictly greater than the previous group. Return an integer denoting the maximum number of groups you can create while satisfying these conditions.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_increasing_groups(usage_limits: Vec<i32>) -> i32 {
    let mut limits = usage_limits;
    limits.sort_unstable();
    // Greedy pool: accumulate limits in sorted order; form next group when pool allows it.
    // This correctly accounts for the constraint that each group needs distinct numbers.
    let mut groups: i64 = 0;
    let mut pool: i64 = 0;
    for l in limits {
      pool += l as i64;
      if pool >= groups + 1 {
        groups += 1;
        pool -= groups;
      }
    }
    groups as i32
  }
}