Skip to content

2517. Maximum Tastiness of Candy Basket 👍

  • Time: $O(\texttt{sort} + n \cdot (\max(\texttt{price}) - \min(\texttt{price})))$
  • Space: $O(\texttt{sort} + 1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int maximumTastiness(vector<int>& price, int k) {
    ranges::sort(price);

    int l = 0;
    int r = ranges::max(price) - ranges::min(price) + 1;

    while (l < r) {
      const int m = (l + r) / 2;
      if (numBaskets(price, m) >= k)
        l = m + 1;
      else
        r = m;
    }

    return l - 1;
  }

 private:
  // Returns the number of baskets we can pick for m tastiness.
  int numBaskets(const vector<int>& price, int m) {
    int baskets = 0;
    int prevPrice = -m;
    for (const int p : price)
      if (p >= prevPrice + m) {
        prevPrice = p;
        ++baskets;
      }
    return baskets;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int maximumTastiness(int[] price, int k) {
    Arrays.sort(price);

    int l = 0;
    int r = Arrays.stream(price).max().getAsInt() - Arrays.stream(price).min().getAsInt() + 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (numBaskets(price, m) >= k)
        l = m + 1;
      else
        r = m;
    }

    return l - 1;
  }

  // Returns the number of baskets we can pick for m tastiness.
  private int numBaskets(int[] price, int m) {
    int baskets = 0;
    int prevPrice = -m;
    for (final int p : price)
      if (p >= prevPrice + m) {
        prevPrice = p;
        ++baskets;
      }
    return baskets;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maximumTastiness(self, price: List[int], k: int) -> int:
    price.sort()

    # Returns true if we can't pick k distinct candies for m tastiness.
    def cantPick(m: int) -> bool:
      baskets = 0
      prevPrice = -m
      for p in price:
        if p >= prevPrice + m:
          prevPrice = p
          baskets += 1
      return baskets < k

    l = bisect.bisect_left(range(max(price) - min(price) + 1), True,
                           key=lambda m: cantPick(m))
    return l - 1