Solution Approach

The solution uses binary search with the first_true_index template pattern combined with a greedy validation function.

Key Insight for Template Adaptation: This is a maximization problem where we want the largest feasible value. To use the first_true_index template, we invert the condition: instead of "can we achieve tastiness x?", we ask "is x infeasible?". Then we find the first infeasible value and subtract 1.

Step 1: Sort the prices

price.sort()

Sorting allows us to work with candies in order of increasing price.

Step 2: Set up binary search with the template

left = 0
right = price[-1] - price[0] + 1  # +1 to include the boundary
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # Returns True when infeasible
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1

Step 3: The inverted feasible function

def feasible(min_diff: int) -> bool:
    count = 0
    last_selected = -min_diff

    for current_price in price:
        if current_price - last_selected >= min_diff:
            last_selected = current_price
            count += 1

    # Return True when infeasible (cannot select k candies)
    return count < k

This greedy function returns True when we CANNOT select k candies with minimum difference of at least x. The pattern of values is: false, false, ..., true, true, ... where the first true marks the first infeasible value.

The algorithm works because:

1. We find first_true_index: the smallest value where we cannot achieve the tastiness
2. The maximum feasible tastiness is first_true_index - 1
3. This maintains the canonical template structure while solving a maximization problem

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).

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. Using Wrong Binary Search Template Variant

A common mistake is using the while left < right pattern with ceiling division instead of the standard first_true_index template.

Why this causes problems:

• Different binary search variants have subtle differences in boundary handling
• Mixing patterns leads to off-by-one errors or infinite loops
• The standard template provides consistency across all binary search problems

Solution: For maximization problems, use the first_true_index template with an inverted condition:

left, right = 0, max_value + 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if not feasible(mid):  # Inverted: True when infeasible
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1  # Maximum feasible value

This maintains the canonical template structure while solving maximization problems.

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.