Maximum elegance of a k length subsequence

Array Hash Table Stack Greedy Sorting Heap (Priority Queue)

28.5% acceptance

Feb 25, 2026

323

You are given a 0-indexed 2D integer array items of length n and an integer k. items[i] = [profiti, categoryi], where profiti and categoryi denote the profit and category of the ith item respectively. Let's define the elegance of a subsequence of items as total_profit + distinct_categories2, where total_profit is the sum of all profits in the subsequence, and distinct_categories is the number of distinct categories from all the categories in the selected subsequence. Your task is to find the maximum elegance from all subsequences of size k in items. Return an integer denoting the maximum elegance of a subsequence of items with size exactly k. Note: A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_maximum_elegance(items: Vec<Vec<i32>>, k: i32) -> i64 {
    use std::collections::HashSet;
    let k = k as usize;
    let mut sorted = items.clone();
    sorted.sort_by(|a, b| b[0].cmp(&a[0]));
    let mut total_profit: i64 = 0;
    let mut categories: HashSet<i32> = HashSet::new();
    let mut dup_profits: Vec<i32> = Vec::new(); // profits of items w/ duplicate categories (in decreasing order)
    for i in 0..k {
      total_profit += sorted[i][0] as i64;
      if !categories.insert(sorted[i][1]) {
        dup_profits.push(sorted[i][0]);
      }
    }
    let mut best = total_profit + (categories.len() as i64).pow(2);
    for i in k..sorted.len() {
      let profit = sorted[i][0];
      let cat = sorted[i][1];
      if categories.contains(&cat) || dup_profits.is_empty() { continue; }
      let removed = dup_profits.pop().unwrap();
      total_profit = total_profit - removed as i64 + profit as i64;
      categories.insert(cat);
      best = best.max(total_profit + (categories.len() as i64).pow(2));
    }
    best
  }
}