Largest values from labels

Array Hash Table Greedy Sorting Counting

64.1% acceptance

Feb 25, 2026

495

637

You are given n item's value and label as two integer arrays values and labels. You are also given two integers numWanted and useLimit. Your task is to find a subset of items with the maximum sum of their values such that: The number of items is at most numWanted. The number of items with the same label is at most useLimit. Return the maximum sum.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_vals_from_labels(values: Vec<i32>, labels: Vec<i32>, num_wanted: i32, use_limit: i32) -> i32 {
    let mut items: Vec<(i32, i32)> = values.into_iter().zip(labels.into_iter()).collect();
    items.sort_unstable_by(|a, b| b.0.cmp(&a.0));
    let mut label_count: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
    let mut sum = 0i32;
    let mut count = 0i32;
    for (v, l) in items {
      if count >= num_wanted { break; }
      let lc = label_count.entry(l).or_insert(0);
      if *lc < use_limit { sum += v; *lc += 1; count += 1; }
    }
    sum
  }
}