Problem Description

You have an array price containing positive integers, where price[i] represents the price of the i-th candy. You also have a positive integer k.

The store sells baskets containing exactly k distinct candies. The tastiness of a candy basket is defined as the smallest absolute difference between the prices of any two candies in that basket.

Your task is to find the maximum possible tastiness value when selecting k distinct candies from the available candies.

Example to understand tastiness:

• If you have a basket with candies priced at [1, 5, 9], the absolute differences between pairs are:
  • |5 - 1| = 4
  • |9 - 5| = 4
  • |9 - 1| = 8
• The tastiness would be min(4, 4, 8) = 4

The goal is to select k candies such that the minimum pairwise price difference is as large as possible.

Key Points:

• You must select exactly k distinct candies
• The tastiness is the minimum difference between any two selected candies
• You want to maximize this tastiness value
• The candies are distinct (you can't pick the same candy twice)

Intuition

When we need to maximize the minimum difference between selected candies, we want to spread out our selections as much as possible. Think of it like placing k points on a number line - to maximize the minimum distance between any two points, we'd want to space them out evenly.

The key insight is that if we sort the prices first, we can transform this into a different problem: instead of finding which candies to select, we can ask "given a minimum difference x, can we select k candies such that every pair has at least x difference?"

This reframing leads us to binary search on the answer. Why? Because:

1. If we can achieve a tastiness of x, we can also achieve any tastiness less than x (by selecting the same candies)
2. If we cannot achieve a tastiness of x, we cannot achieve any tastiness greater than x

This monotonic property makes binary search perfect for this problem.

The search space for our answer is between:

• Minimum: 0 (worst case, though we could have identical prices)
• Maximum: price[-1] - price[0] (the difference between the most and least expensive candy after sorting)

For each candidate tastiness value mid, we greedily check if we can select k candies with minimum difference of at least mid. The greedy strategy works because once we sort the prices, we can always start with the first candy and keep selecting the next candy that is at least mid distance away. If we can find k such candies, then mid is achievable; otherwise, we need to try a smaller value.

The greedy selection is optimal because selecting candies that are closer together than necessary doesn't help us - we want to use our "budget" of candies efficiently by spreading them out as much as the current mid value requires.

Learn more about Greedy, Binary Search and Sorting patterns.

Solution Approach

The solution uses binary search combined with a greedy validation function. Here's how it works:

Step 1: Sort the prices

price.sort()

Sorting allows us to work with candies in order of increasing price, which makes the greedy selection strategy work.

Step 2: Set up binary search boundaries

l, r = 0, price[-1] - price[0]

• Left boundary l = 0: minimum possible tastiness
• Right boundary r = price[-1] - price[0]: maximum possible tastiness (difference between most and least expensive candy)

Step 3: Binary search for the maximum valid tastiness

while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1

We use binary search to find the largest tastiness value that allows selecting k candies. The (l + r + 1) >> 1 is equivalent to (l + r + 1) // 2, which calculates the ceiling of the midpoint to avoid infinite loops when l and r are adjacent.

Step 4: The validation function check(x)

def check(x: int) -> bool:
    cnt, pre = 0, -x
    for cur in price:
        if cur - pre >= x:
            pre = cur
            cnt += 1
    return cnt >= k

This greedy function checks if we can select k candies with minimum difference of at least x:

• Initialize cnt = 0 (count of selected candies) and pre = -x (previous selected candy price, initialized to ensure first candy is always selected)
• Iterate through sorted prices
• Select a candy if its price difference from the previously selected candy is at least x
• Update pre to current candy's price and increment cnt
• Return True if we can select at least k candies, False otherwise

The algorithm works because:

1. If we can achieve tastiness x, the check function returns True, so we try a larger value (l = mid)
2. If we cannot achieve tastiness x, we need to try a smaller value (r = mid - 1)
3. The loop continues until l == r, which gives us the maximum achievable tastiness

Time Complexity: O(n log(max_price - min_price)) where n is the length of the price array Space Complexity: O(1) excluding the sorting space

Example Walkthrough

Let's walk through an example with price = [13, 5, 1, 8, 21, 2] and k = 3.

Step 1: Sort the prices After sorting: price = [1, 2, 5, 8, 13, 21]

Step 2: Initialize binary search boundaries

• l = 0 (minimum possible tastiness)
• r = 21 - 1 = 20 (maximum possible tastiness)

Step 3: Binary search iterations

Iteration 1:

• mid = (0 + 20 + 1) >> 1 = 10
• Check if we can achieve tastiness of 10:
  • Start with pre = -10, cnt = 0
  • Candy at price 1: 1 - (-10) = 11 >= 10 ✓ Select it. pre = 1, cnt = 1
  • Candy at price 2: 2 - 1 = 1 < 10 ✗ Skip
  • Candy at price 5: 5 - 1 = 4 < 10 ✗ Skip
  • Candy at price 8: 8 - 1 = 7 < 10 ✗ Skip
  • Candy at price 13: 13 - 1 = 12 >= 10 ✓ Select it. pre = 13, cnt = 2
  • Candy at price 21: 21 - 13 = 8 < 10 ✗ Skip
  • Result: cnt = 2 < 3 → Cannot achieve tastiness of 10
• Update: r = 10 - 1 = 9

Iteration 2:

• mid = (0 + 9 + 1) >> 1 = 5
• Check if we can achieve tastiness of 5:
  • Start with pre = -5, cnt = 0
  • Candy at price 1: 1 - (-5) = 6 >= 5 ✓ Select it. pre = 1, cnt = 1
  • Candy at price 2: 2 - 1 = 1 < 5 ✗ Skip
  • Candy at price 5: 5 - 1 = 4 < 5 ✗ Skip
  • Candy at price 8: 8 - 1 = 7 >= 5 ✓ Select it. pre = 8, cnt = 2
  • Candy at price 13: 13 - 8 = 5 >= 5 ✓ Select it. pre = 13, cnt = 3
  • Candy at price 21: We already have 3 candies
  • Result: cnt = 3 >= 3 → Can achieve tastiness of 5
• Update: l = 5

Iteration 3:

• mid = (5 + 9 + 1) >> 1 = 7
• Check if we can achieve tastiness of 7:
  • Start with pre = -7, cnt = 0
  • Candy at price 1: 1 - (-7) = 8 >= 7 ✓ Select it. pre = 1, cnt = 1
  • Candy at price 2: 2 - 1 = 1 < 7 ✗ Skip
  • Candy at price 5: 5 - 1 = 4 < 7 ✗ Skip
  • Candy at price 8: 8 - 1 = 7 >= 7 ✓ Select it. pre = 8, cnt = 2
  • Candy at price 13: 13 - 8 = 5 < 7 ✗ Skip
  • Candy at price 21: 21 - 8 = 13 >= 7 ✓ Select it. pre = 21, cnt = 3
  • Result: cnt = 3 >= 3 → Can achieve tastiness of 7
• Update: l = 7

Iteration 4:

• mid = (7 + 9 + 1) >> 1 = 8
• Check if we can achieve tastiness of 8:
  • Start with pre = -8, cnt = 0
  • Candy at price 1: 1 - (-8) = 9 >= 8 ✓ Select it. pre = 1, cnt = 1
  • Candy at price 2: 2 - 1 = 1 < 8 ✗ Skip
  • Candy at price 5: 5 - 1 = 4 < 8 ✗ Skip
  • Candy at price 8: 8 - 1 = 7 < 8 ✗ Skip
  • Candy at price 13: 13 - 1 = 12 >= 8 ✓ Select it. pre = 13, cnt = 2
  • Candy at price 21: 21 - 13 = 8 >= 8 ✓ Select it. pre = 21, cnt = 3
  • Result: cnt = 3 >= 3 → Can achieve tastiness of 8
• Update: l = 8

Iteration 5:

• mid = (8 + 9 + 1) >> 1 = 9
• Check if we can achieve tastiness of 9:
  • Start with pre = -9, cnt = 0
  • Candy at price 1: 1 - (-9) = 10 >= 9 ✓ Select it. pre = 1, cnt = 1
  • Candy at price 2: 2 - 1 = 1 < 9 ✗ Skip
  • Candy at price 5: 5 - 1 = 4 < 9 ✗ Skip
  • Candy at price 8: 8 - 1 = 7 < 9 ✗ Skip
  • Candy at price 13: 13 - 1 = 12 >= 9 ✓ Select it. pre = 13, cnt = 2
  • Candy at price 21: 21 - 13 = 8 < 9 ✗ Skip
  • Result: cnt = 2 < 3 → Cannot achieve tastiness of 9
• Update: r = 9 - 1 = 8

Final result: l = r = 8

The maximum tastiness is 8, achieved by selecting candies with prices [1, 13, 21]. The minimum difference between any pair is indeed 8 (21 - 13 = 8).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n + n log(max_price))

The time complexity consists of two main parts:

• Sorting the price array takes O(n log n) where n is the length of the price list
• Binary search runs in O(log(max_price - min_price)) iterations, where max_price - min_price represents the search space
• For each binary search iteration, the check function is called which takes O(n) time as it iterates through all prices once
• Therefore, the binary search portion contributes O(n * log(max_price - min_price))
• Since max_price - min_price ≤ max_price, we can simplify this to O(n log(max_price))
• Overall: O(n log n + n log(max_price))

Space Complexity: O(1) or O(log n)

• The algorithm uses only a constant amount of extra space for variables (l, r, mid, cnt, pre, cur)
• The sorting operation might use O(log n) space if an in-place sorting algorithm like quicksort is used (for recursion stack)
• If the sorting is done using Timsort (Python's default), it would use O(n) auxiliary space in the worst case, but typically O(log n)
• Excluding the sorting space, the algorithm itself uses O(1) extra space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Midpoint Calculation

One of the most common mistakes in this problem is using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 when updating left = mid.

Why this causes problems:

• When left and right are adjacent (e.g., left = 3, right = 4), using floor division gives mid = 3
• If the check passes, we set left = mid = 3, creating an infinite loop
• The ceiling division ensures mid = 4, allowing the search to progress

Solution: Always use mid = (left + right + 1) // 2 when the update condition is left = mid. Alternatively, use the template:

while left < right:
    mid = (left + right) // 2
    if can_achieve_min_diff(mid + 1):  # Check mid + 1 instead
        left = mid + 1
    else:
        right = mid

2. Incorrect Greedy Validation Logic

Another pitfall is incorrectly implementing the validation function, particularly:

• Starting with last_selected = 0 instead of last_selected = -min_diff
• Using <= instead of >= in the comparison
• Forgetting to update last_selected after selecting a candy

Why this matters:

• Starting with last_selected = 0 might incorrectly reject the first candy if its price is less than min_diff
• The greedy approach only works because we're iterating through sorted prices

Solution: Initialize last_selected = -min_diff or use a flag for the first candy:

def can_achieve_min_diff(min_diff):
    count = 1  # Start with first candy selected
    last_selected = price[0]
  
    for i in range(1, len(price)):
        if price[i] - last_selected >= min_diff:
            last_selected = price[i]
            count += 1
          
    return count >= k

3. Forgetting to Sort the Array

The greedy approach only works on a sorted array. Without sorting, you cannot guarantee that selecting the next valid candy maintains the minimum difference constraint for all previously selected candies.

Solution: Always sort the price array before applying the binary search and greedy validation.