# Maximum Tastiness of Candy Basket
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-tastiness-of-candy-basket)
Canonical: https://scaleengineer.com/dsa/problems/maximum-tastiness-of-candy-basket
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [eBay](https://scaleengineer.com/companies/ebay), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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._

**Example 1:**

**Input:** price = [13,5,1,8,21,2], k = 3
**Output:** 8
**Explanation:** Choose the candies with the prices [13,5,21].
The tastiness of the candy basket is: min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8.
It can be proven that 8 is the maximum tastiness that can be achieved.

**Example 2:**

**Input:** price = [1,3,1], k = 2
**Output:** 2
**Explanation:** Choose the candies with the prices [1,3].
The tastiness of the candy basket is: min(|1 - 3|) = min(2) = 2.
It can be proven that 2 is the maximum tastiness that can be achieved.

**Example 3:**

**Input:** price = [7,7,7,7], k = 2
**Output:** 0
**Explanation:** Choosing any two distinct candies from the candies we have will result in a tastiness of 0.

**Constraints:**

* `2 <= k <= price.length <= 105`
* `1 <= price[i] <= 109`

# Approaches
## Brute Force with Combinations
This approach directly translates the problem statement into a search algorithm. It involves systematically generating every possible basket of `k` candies, calculating the tastiness for each one, and keeping track of the highest tastiness found. While straightforward, its computational cost is prohibitive.
**Time:** O(C(N, k) * k log k)

Where `N` is the length of the `price` array and `C(N, k)` is the number of combinations (`N! / (k! * (N-k)!)`). Generating all combinations is exponential. For each combination, we sort it in `O(k log k)` time. This complexity is far too high for the given constraints. · **Space:** O(k)

This space is used to store the current combination being built and for the recursion stack. The depth of the recursion is at most `k`.
**Pros:** Simple to conceptualize and follows the problem definition directly.
**Cons:** Extremely slow and inefficient.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints due to the exponential number of combinations.
### Explanation
The core idea is to perform an exhaustive search over all possible subsets of size `k` from the `price` array. We can implement this using a recursive function that builds a combination step by step.

For every complete combination of `k` candies, we determine its tastiness. The tastiness is defined as the smallest absolute difference between the prices of any two candies in the basket. An easy way to compute this is to first sort the `k` prices in the basket and then iterate through the sorted prices to find the minimum difference between adjacent elements. This minimum difference is the tastiness for that specific basket.

We maintain a global variable, `max_tastiness`, which is updated whenever we find a basket with a tastiness greater than the current maximum. After exploring all `C(N, k)` combinations, this variable will hold the final answer.

```java
// Note: This code is for demonstration and will be too slow for the problem constraints.
class Solution {
    int maxTastiness = 0;
    int k;
    int[] price;

    public int maximumTastiness(int[] price, int k) {
        this.k = k;
        this.price = price;
        // Using a list of prices for the current basket
        findCombinations(0, new java.util.ArrayList<>());
        return maxTastiness;
    }

    private void findCombinations(int start, java.util.List<Integer> currentBasketPrices) {
        if (currentBasketPrices.size() == k) {
            // A full basket is formed, calculate its tastiness
            java.util.Collections.sort(currentBasketPrices);
            int minDiff = Integer.MAX_VALUE;
            for (int i = 0; i < currentBasketPrices.size() - 1; i++) {
                minDiff = Math.min(minDiff, currentBasketPrices.get(i + 1) - currentBasketPrices.get(i));
            }
            maxTastiness = Math.max(maxTastiness, minDiff);
            return;
        }

        // Explore further combinations
        for (int i = start; i < price.length; i++) {
            currentBasketPrices.add(price[i]);
            findCombinations(i + 1, currentBasketPrices);
            currentBasketPrices.remove(currentBasketPrices.size() - 1); // Backtrack
        }
    }
}
```
### Algorithm
- Initialize `max_tastiness` to 0.
- Generate all unique combinations of `k` candies from the `price` array. A recursive backtracking approach is suitable for this.
- For each combination (a basket of `k` candies):
  1.  Sort the prices within the current basket.
  2.  Calculate the tastiness by finding the minimum difference between any two adjacent prices in the sorted basket.
  3.  Update `max_tastiness = max(max_tastiness, current_tastiness)`.
- After iterating through all possible combinations, return `max_tastiness`.

## Binary Search on the Answer
A much more efficient approach leverages binary search on the answer. The problem asks to maximize a minimum value (the tastiness). This structure suggests that if we can achieve a tastiness of `t`, we can also achieve any tastiness less than `t`. This monotonic property allows us to binary search for the optimal tastiness value.

The core of this approach is a helper function that can efficiently determine if it's possible to form a basket with a given minimum tastiness. By combining this check with binary search, we can quickly narrow down the search space and find the maximum possible tastiness.
**Time:** O(N log N + N log R)

Where `N` is `price.length` and `R` is the range of prices (`max_price - min_price`). Sorting takes `O(N log N)`. The binary search performs `O(log R)` iterations, and each iteration involves a call to `canAchieve`, which takes `O(N)` time. The total time is therefore `O(N log N + N log R)`. · **Space:** O(log N) or O(N)

The space complexity is dominated by the sorting algorithm. In-place quicksort uses `O(log N)` space for its recursion stack, while merge sort would use `O(N)`. The binary search itself uses `O(1)` extra space.
**Pros:** Highly efficient and optimal.; Scales well for large inputs, easily passing the given constraints.
**Cons:** The logic is less direct than brute force and requires understanding the concept of binary searching on an answer space.
### Explanation
The key insight is to reframe the problem from "find the maximum tastiness" to "is it possible to achieve a tastiness of `x`?". If we can answer this decision problem efficiently, we can use binary search to find the maximum `x` for which the answer is yes.

**1. Sorting:**
First, we sort the `price` array. This allows us to check for differences greedily and efficiently. Let the sorted array be `p'`. The tastiness of any basket of `k` candies `{c_1, c_2, ..., c_k}` with `c_1 < c_2 < ... < c_k` is determined by the minimum of `c_{i+1} - c_i`.

**2. The `canAchieve(tastiness)` check:**
To check if a given `tastiness` is achievable, we use a greedy strategy on the sorted `price` array:
- Pick the first candy (`price[0]`).
- Iterate through the rest of the array. To maintain the minimum difference, the next candy we pick must have a price of at least `(price of last picked candy) + tastiness`.
- We greedily select the very next candy that satisfies this condition.
- We count how many candies we can pick this way. If the count is at least `k`, then the given `tastiness` is achievable.

**3. Binary Search:**
We binary search over the possible range of answers. The lowest possible tastiness is 0, and the highest is the difference between the maximum and minimum prices in the array.
- We repeatedly take the middle value `mid` of our current search range and use `canAchieve(mid)` to test it.
- If it's achievable, we know `mid` is a potential answer, and we try for a better (larger) one by searching in the upper half: `low = mid + 1`.
- If it's not achievable, `mid` is too high, so we must search in the lower half: `high = mid - 1`.

This process efficiently converges to the maximum possible tastiness.

```java
import java.util.Arrays;

class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int n = price.length;
        int low = 0;
        int high = price[n - 1] - price[0];
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canAchieve(mid, price, k)) {
                // This tastiness is achievable, so it's a potential answer.
                // We try for an even larger tastiness.
                ans = mid;
                low = mid + 1;
            } else {
                // This tastiness is too high, we need to try a smaller one.
                high = mid - 1;
            }
        }
        return ans;
    }

    // Helper function to check if we can pick k candies with at least `tastiness` difference.
    private boolean canAchieve(int tastiness, int[] price, int k) {
        int count = 1; // We always pick the first candy
        int lastPrice = price[0];
        for (int i = 1; i < price.length; i++) {
            if (price[i] >= lastPrice + tastiness) {
                count++;
                lastPrice = price[i];
            }
        }
        return count >= k;
    }
}
```
### Algorithm
- First, sort the `price` array in non-decreasing order. This is crucial for the greedy checking strategy.
- Define a search space for the answer (the tastiness). The minimum possible tastiness is `0`, and the maximum is `price[n-1] - price[0]`.
- Perform a binary search on this range `[low, high]`.
- For each `mid` value (a potential tastiness) in the binary search:
  - Check if it's possible to select `k` candies with at least a `mid` price difference. This is done with a greedy helper function, `canAchieve(tastiness)`.
  - The `canAchieve` function works by iterating through the sorted `price` array. It greedily picks candies, always choosing the next candy that is at least `tastiness` away from the previously picked one.
  - If `canAchieve(mid)` returns `true`, it means a tastiness of `mid` is possible. We store `mid` as a potential answer and try for an even higher tastiness by setting `low = mid + 1`.
  - If `canAchieve(mid)` returns `false`, the tastiness `mid` is too high. We must search for a smaller one by setting `high = mid - 1`.
- The last successfully validated `mid` value is the maximum possible tastiness.

# Solutions
### CSharp

```csharp
public class Solution { public int MaximumTastiness ( int [] price , int k ) { Array . Sort ( price ); int l = 0 , r = price [ price . Length - 1 ] - price [ 0 ]; while ( l < r ) { int mid = ( l + r + 1 ) >> 1 ; if ( check ( price , mid , k )) { l = mid ; } else { r = mid - 1 ; } } return l ; } private bool check ( int [] price , int x , int k ) { int cnt = 0 , pre = - x ; foreach ( int cur in price ) { if ( cur - pre >= x ) { ++ cnt ; pre = cur ; } } return cnt >= k ; } }
```

### Java

```java
class Solution {
public
  int maximumTastiness(int[] price, int k) {
    Arrays.sort(price);
    int l = 0, r = price[price.length - 1] - price[0];
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(price, k, mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
private
  boolean check(int[] price, int k, int x) {
    int cnt = 0, pre = -x;
    for (int cur : price) {
      if (cur - pre >= x) {
        pre = cur;
        ++cnt;
      }
    }
    return cnt >= k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumTastiness(vector<int> &price, int k) {
    sort(price.begin(), price.end());
    int l = 0, r = price.back() - price[0];
    auto check = [&](int x) -> bool {
      int cnt = 0, pre = -x;
      for (int &cur : price) {
        if (cur - pre >= x) {
          pre = cur;
          ++cnt;
        }
      }
      return cnt >= k;
    };
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int: def check(x: int) -> bool: cnt, pre = 0, - x for cur in price: if cur - pre >= x: pre = cur cnt += 1 return cnt >= k price . sort() l, r = 0, price[- 1] - price[0] while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l

```