Maximum tastiness of candy basket

Array Binary Search Greedy Sorting

67.9% acceptance

Feb 25, 2026

1058

184

You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k. The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket. Return the maximum tastiness of a candy basket.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_tastiness(mut price: Vec<i32>, k: i32) -> i32 {
    price.sort_unstable();

    let can_pick = |min_gap: i32| -> bool {
      let mut count = 1i32;
      let mut prev = price[0];
      for &p in &price[1..] {
        if p - prev >= min_gap {
          count += 1;
          prev = p;
          if count == k {
            return true;
          }
        }
      }
      count >= k
    };

    let mut lo = 0i32;
    let mut hi = price[price.len() - 1] - price[0];
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if can_pick(mid) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo
  }
}