Maximum Tastiness of Candy Basket

Maximum Tastiness of Candy Basket

1. What is this problem about?

The Maximum Tastiness of Candy Basket problem asks you to pick k candies from a set of candies, each with a given price. The "tastiness" of a chosen basket is defined as the minimum absolute difference between the prices of any two candies in that basket. Your goal is to pick k candies such that this tastiness value is as large as possible. It is a classic "maximize the minimum" problem.

2. Why is this asked in interviews?

This "Maximum Tastiness of Candy Basket interview question" is popular at companies like Amazon, eBay, and PhonePe. It tests whether a candidate can recognize the "Binary Search on Answer" pattern. This pattern is essential for problems where finding the answer directly is hard, but checking if a specific answer is "possible" is relatively easy. It evaluates your ability to combine sorting, binary search, and greedy validation.

3. Algorithmic pattern used

The "Array, Sorting, Binary Search, Greedy interview pattern" is used here.

1. Sort the candy prices.
2. The possible tastiness ranges from 0 to the difference between the max and min price.
3. Perform a binary search on this range. For a target tastiness mid:
   • Can we pick k candies such that every pair has a difference >= mid?
   • This is checked greedily: pick the first candy, then pick the next candy that is at least mid away from the previous one, and so on.
   • If we can pick at least k candies, mid is possible.

4. Example explanation

Prices: [1, 3, 21, 5, 8], k = 3

• Sorted: [1, 3, 5, 8, 21]
• Check tastiness = 5:
  • Pick 1. Next must be >= 1+5=6. Pick 8. Next must be >= 8+5=13. Pick 21.
  • We picked 3 candies! So 5 is possible.
• Check tastiness = 10:
  • Pick 1. Next must be >= 1+10=11. Pick 21.
  • Only picked 2 candies. 10 is NOT possible. We continue binary search to find the largest possible value.

5. Common mistakes candidates make

One major mistake in the "Maximum Tastiness of Candy Basket coding problem" is trying to use dynamic programming or a nested loop to find the candies, which would be extremely slow. Another error is not sorting the array before starting the greedy check—sorting is what allows the greedy "pick next possible" strategy to work correctly. Candidates also sometimes get the binary search conditions wrong (e.g., when to move the low vs high pointers).

6. Interview preparation tip

Memorize the "Maximize the Minimum" trigger. Whenever a problem asks you to maximize the minimum distance/difference/value, it is almost certainly a Binary Search on Answer problem. Get very comfortable with the greedy isPossible function, as that is the engine that drives the binary search. Being able to explain why sorting the input helps the greedy check will demonstrate a deep understanding of the algorithm's mechanics.