2600. Maximum Tastiness Of Candy Basket¶

Difficulty: Medium

2600. Maximum Tastiness of Candy Basket

Medium

You are given an array of positive integers price where price[i] denotes the price of the i^th 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 <= 10⁵
1 <= price[i] <= 10⁹

Solution¶

import java.util.Arrays;

class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int low = 0, high = (int)(1e9 + 10), ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, price, k)) {
                ans = mid;
                low = mid + 1;
            } else
                high = mid - 1;
        }
        return ans;
    }
    private boolean ok(int target, int arr[], int k) {
        int n = arr.length;
        k--;
        int current = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] - current >= target) {
                current = arr[i];
                k--;
                if (k == 0)
                    return true;
            }
        }
        return false;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here