Maximum Tastiness of Candy Basket

Medium
1379.

Maximum Tastiness of Candy Basket

Maximum Tastiness of Candy Basket is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and PhonePe interviews.

A candy shop lists price[i] for candy i. A basket holds exactly k different candies (different indices; two candies may share a price).

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.

Example 1

Input
price = [13,5,1,8,21,2], k = 3
Output
8
Explanation
Take the candies priced 13, 5 and 21: the closest pair is 13 and 5, eight apart.

Example 2

Input
price = [1,3,1], k = 2
Output
2

Example 3

Input
price = [7,7,7,7], k = 2
Output
0
Explanation
Every pair costs the same.

Constraints

  • 2 <= k <= price.length <= 10^5
  • 1 <= price[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} price
 * @param {number} k
 * @return {number}
 */
var maximumTastiness = function(price, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Tastiness of Candy Basket — Problem & Solution

Maximum Tastiness of Candy Basket solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Tastiness of Candy Basket is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and PhonePe interviews.

Problem statement

A candy shop lists price[i] for candy i. A basket holds exactly k different candies (different indices; two candies may share a price).

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.

Example 1

Input: price = [13,5,1,8,21,2], k = 3
Output: 8
Explanation: Take the candies priced 13, 5 and 21: the closest pair is 13 and 5, eight apart.

Example 2

Input: price = [1,3,1], k = 2
Output: 2

Example 3

Input: price = [7,7,7,7], k = 2
Output: 0
Explanation: Every pair costs the same.

Constraints

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

Hints for Maximum Tastiness of Candy Basket

  1. Hint 1

    Sorting the prices loses nothing — tastiness only depends on the multiset of chosen prices.

  2. Hint 2

    Ask instead: can you pick k candies whose sorted neighbours are all at least d apart? Larger d only makes it harder.

  3. Hint 3

    For a fixed d, pick greedily from the cheapest candy, taking the next price that is at least d above the last pick; binary-search the largest d that still yields k picks.

How to solve Maximum Tastiness of Candy Basket

Binary search on the answer d. Whether k candies can be spaced at least d apart is decided by a greedy sweep over the sorted prices, and that test is monotone in d.

Approach

  1. Sort price.
  2. canSpace(d): take the first price, then walk right and take every price that is at least d above the last one taken; succeed if at least k are taken.
  3. Binary-search the largest d in [0, price[n-1] - price[0]] with canSpace(d) true (using the upper middle so the loop advances).
  4. Return that d.

Why it works

For a fixed d, taking the smallest price first is never worse: any valid selection can swap its first pick for the global minimum and stay valid, and the same exchange argument applies to every subsequent pick (the earliest admissible price leaves the most room to the right). So the greedy count is the maximum number of candies spaced by d. If d works, every smaller d works, so the largest feasible d is a clean threshold.

Complexity

  • Time — O(n log n + n log R) with R the price range
  • Space — O(n) for the sorted copy

Pitfalls

  • Compare with price[i] - last >= d; writing last + d can overflow 32-bit when both are near 10^9.
  • Duplicate prices are allowed, so the answer can be 0.
  • Use lo + (hi - lo + 1) / 2 when the feasible branch sets lo = mid.

Reference solution

Python

from typing import List

def maximumTastiness(price: List[int], k: int) -> int:
    p = sorted(price)

    def can_space(d):
        taken, last = 1, p[0]
        for x in p:
            if x - last >= d:
                taken += 1
                last = x
                if taken >= k:
                    return True
        return taken >= k

    lo, hi = 0, p[-1] - p[0]
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if can_space(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Java

public static int maximumTastiness(int[] price, int k) {
    int[] p = price.clone();
    Arrays.sort(p);
    int lo = 0, hi = p[p.length - 1] - p[0];
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        int taken = 1, last = p[0];
        for (int i = 1; i < p.length && taken < k; i++) {
            if (p[i] - last >= mid) { taken++; last = p[i]; }
        }
        if (taken >= k) lo = mid; else hi = mid - 1;
    }
    return lo;
}

C++

int maximumTastiness(vector<int>& price, int k) {
    vector<int> p(price);
    sort(p.begin(), p.end());
    int lo = 0, hi = p.back() - p[0];
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        int taken = 1, last = p[0];
        for (int i = 1; i < (int)p.size() && taken < k; i++) {
            if (p[i] - last >= mid) { taken++; last = p[i]; }
        }
        if (taken >= k) lo = mid; else hi = mid - 1;
    }
    return lo;
}

JavaScript

var maximumTastiness = function(price, k) {
    var p = price.slice().sort(function(a, b) { return a - b; });
    var canSpace = function(d) {
        var taken = 1, last = p[0];
        for (var i = 1; i < p.length; i++) {
            if (p[i] - last >= d) {
                taken++;
                last = p[i];
                if (taken >= k) return true;
            }
        }
        return taken >= k;
    };
    var lo = 0, hi = p[p.length - 1] - p[0];
    while (lo < hi) {
        var mid = lo + Math.floor((hi - lo + 1) / 2);
        if (canSpace(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms