Maximum Tastiness of Candy Basket

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Reported atPhonePe

Maximum Tastiness of Candy Basket is a medium binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the answer), runs in O(n log n + n log M) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every pairwise difference) up.

Problem

A shop sells candies, and price[i] is the price of the i-th candy. You want to put together a basket of exactly k different candies (different indices; their prices may be equal).

The tastiness of a basket is the smallest absolute difference between the prices of any two candies in it. Return the largest tastiness any basket of k candies can have.

Examples

Example 1

Input
price = [20, 3, 11, 7, 15, 1], k = 3
Output
9
Why
Pick the prices 1, 11 and 20. The closest pair is 11 and 20, which differ by 9, and no choice of three does better.

Example 2

Input
price = [4, 9, 4], k = 2
Output
5
Why
Taking 4 and 9 gives a difference of 5; taking the two 4s would give 0.

Example 3

Input
price = [6, 6, 6, 6], k = 3
Output
0
Why
All prices are equal, so any two chosen candies differ by 0.

Constraints

  • 2 <= k <= price.length <= 10^5
  • 1 <= price[i] <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every pairwise difference)O(n³)O(1)
Optimal (binary search on the answer)O(n log n + n log M)O(1)

1Brute force (try every pairwise difference)

TimeO(n³)There are O(n²) candidate differences and each greedy check is O(n).
SpaceO(1)Only counters besides the sort.

The best tastiness is always the difference of some pair of prices, so collect every pairwise difference and test each one as a candidate gap. A candidate d is feasible when a greedy scan over the sorted prices (take the first price, then the next price at least d above the last taken one) collects k candies. Return the largest feasible candidate.

  1. Sort price.
  2. For every pair i < j, let d = price[j] - price[i].
  3. Greedy check: take price[0], then every price that is at least d above the last taken one; count them.
  4. If the count reaches k, update the answer with d.
  5. Return the best d found.
class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int n = price.length, best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int d = price[j] - price[i];
                if (d > best && canPick(price, k, d)) best = d;
            }
        return best;
    }

    private boolean canPick(int[] price, int k, int d) {
        int count = 1, last = price[0];
        for (int i = 1; i < price.length && count < k; i++)
            if (price[i] - last >= d) {
                count++;
                last = price[i];
            }
        return count >= k;
    }
}

2Optimal (binary search on the answer)

TimeO(n log n + n log M)Sorting costs n log n, and each of the log M binary-search steps (M = max - min) runs an O(n) greedy check.
SpaceO(1)Only a few variables besides the in-place sort.

Feasibility is monotonic in d: if you can pick k candies with all gaps at least d, you can also do it for any smaller gap. So binary search d over [0, max - min], using the same greedy scan to test each middle value. Taking the cheapest remaining candy that is far enough from the last one is always safe, because it leaves the most room for the rest.

  1. Sort price.
  2. lo = 0, hi = price[n-1] - price[0].
  3. While lo < hi: mid = lo + (hi - lo + 1) / 2.
  4. If the greedy scan picks at least k candies with gap mid, set lo = mid; otherwise hi = mid - 1.
  5. Return lo.
class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int lo = 0, hi = price[price.length - 1] - price[0];
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (canPick(price, k, mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    private boolean canPick(int[] price, int k, int d) {
        int count = 1, last = price[0];
        for (int i = 1; i < price.length && count < k; i++)
            if (price[i] - last >= d) {
                count++;
                last = price[i];
            }
        return count >= k;
    }
}

Edge cases to test

  • k = 2: the answer is simply max - min
  • k = price.length: every candy is taken, so the answer is the smallest gap between neighbours after sorting
  • Duplicate prices, which can force the answer down to 0
  • Prices near 10^9, where differences must not overflow

Hints

Hint 1

Only the relative order of prices matters, so sort them first. The tastiness of a chosen set is then the smallest gap between consecutive chosen prices.

Hint 2

Turn the question around: for a fixed gap d, can you pick k candies whose consecutive gaps are all at least d? A greedy left-to-right pick answers that.

Hint 3

If gap d is achievable, every smaller gap is too. That monotonic yes/no answer is exactly what binary search on the answer needs.

FAQ

What is the best time complexity for Maximum Tastiness of Candy Basket?

Optimal (binary search on the answer) runs in O(n log n + n log M) time and O(1) extra space. Sorting costs n log n, and each of the log M binary-search steps (M = max - min) runs an O(n) greedy check.

Which pattern does Maximum Tastiness of Candy Basket use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.

Is there a brute force solution for Maximum Tastiness of Candy Basket?

Yes. Brute force (try every pairwise difference) takes O(n³) time and O(1) space. The best tastiness is always the difference of some pair of prices, so collect every pairwise difference and test each one as a candidate gap.

Which edge cases should I test for Maximum Tastiness of Candy Basket?

k = 2: the answer is simply max - min; k = price.length: every candy is taken, so the answer is the smallest gap between neighbours after sorting; Duplicate prices, which can force the answer down to 0; Prices near 10^9, where differences must not overflow.