Maximum Tastiness of Candy Basket - Practice Coding Problems

Maximum Tastiness of Candy Basket - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: price = [13,5,1,8,21], k = 3

› Output: 8

💡 Note: Choose candies with prices [13, 5, 21]. The tastiness is min(|13-5|, |13-21|, |5-21|) = min(8, 8, 16) = 8.

Example 2 — Minimum Size

$ Input: price = [4,2,5], k = 2

› Output: 1

💡 Note: Choose candies with prices [4, 5]. The tastiness is |4-5| = 1. This is optimal since choosing [2,4] or [2,5] gives tastiness 2 or 3.

Example 3 — All Candies

$ Input: price = [1,3,1], k = 3

› Output: 0

💡 Note: We must choose all candies [1,3,1]. The tastiness is min(|1-3|, |1-1|, |3-1|) = min(2, 0, 2) = 0.

Constraints

2 ≤ price.length ≤ 10⁵
1 ≤ price[i] ≤ 10⁹
2 ≤ k ≤ price.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of candy prices and number k of candies to select

Process

Sort prices, then binary search on tastiness value

Output

Maximum tastiness (minimum difference) achievable

Key Takeaway

🎯 Key Insight: Sort the prices first, then binary search on the tastiness value while greedily selecting candies

Asked in

G Google 25 a Amazon 18 M Meta 12

The key insight is to sort the candy prices first, then use binary search on the answer space (possible tastiness values). For each candidate tastiness, we greedily check if k candies can be selected with that minimum difference. Best approach is Binary Search on Answer with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n log n + n log(max_price))	O(1)	Binary search on the maximum possible tastiness value
Brute Force - Try All Combinations	O(C(n,k) × k²)	O(k)	Generate all possible k-candy combinations and find maximum tastiness

Binary Search on Answer — Algorithm Steps

Sort the candy prices
Binary search on tastiness value (0 to max_price - min_price)
For each candidate, greedily select k candies with minimum gap >= candidate
Return the maximum valid tastiness

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Search Range

Sort prices, search tastiness from 0 to max_price-min_price

Greedy Check

For each candidate tastiness, greedily select k candies

Binary Search

Narrow down to maximum valid tastiness

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int canSelect(int* price, int priceSize, int k, int minDiff) {
    int count = 1;
    int lastSelected = price[0];
    for (int i = 1; i < priceSize; i++) {
        if (price[i] - lastSelected >= minDiff) {
            count++;
            lastSelected = price[i];
            if (count == k) return 1;
        }
    }
    return 0;
}

int solution(int* price, int priceSize, int k) {
    qsort(price, priceSize, sizeof(int), compare);
    
    int left = 0, right = price[priceSize - 1] - price[0];
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canSelect(price, priceSize, k, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int price[1000];
    int priceSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            price[priceSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(price, priceSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + n log(max_price))

Sorting takes O(n log n), binary search takes O(log(max_price)) iterations, each with O(n) greedy check

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables, no extra data structures needed

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler