Anchored Spice Flight

Maximum minimum pairwise gap among k array elements with a required index

MediumBinary SearchGreedySorting

A recipe app is assembling a tasting flight of exactly k different recipe variants. Each variant has an integer spice intensity, given in intensities.

The variant at index anchor is the reference recipe and must be included in the flight. All indices are zero-based. Two variants at different indices are different recipes, even if their intensities are equal.

The flight's separation is the smallest absolute difference in intensity between any two selected variants.

Return the largest separation achievable by selecting exactly k variants, including the reference recipe.

Examples

Example 1

Input: intensities = [12,2,20,7,30], k = 3, anchor = 0
Output: 10

The reference recipe has intensity 12. Selecting the variants with intensities 2, 12, and 30 gives the widest possible smallest gap while retaining that reference.

Example 2

Input: intensities = [0,10,11,20], k = 3, anchor = 2
Output: 9

The reference has intensity 11. Selecting intensities 0, 11, and 20 is optimal. The otherwise attractive selection of 0, 10, and 20 is not allowed because it omits the reference.

Example 3

Input: intensities = [5,5,12,20], k = 4, anchor = 1
Output: 0

Every variant must be selected, including two distinct variants with the same intensity. Those two variants determine the flight's smallest gap.

Constraints

  • 2 <= len(intensities) <= 6000
  • 0 <= intensities[i] <= 10^9
  • 2 <= k <= len(intensities)
  • 0 <= anchor < len(intensities)
  • The input intensities are not necessarily sorted.

Sorting takes O(n log n). Each feasibility check takes O(n), and binary search uses O(log(R + 1)) checks, where R is the intensity range. Total time is O(n log n + n log(R + 1)), with O(n) extra space. For a fixed gap, taking the closest eligible variant on each side of the anchor leaves the most room for further selections. Any selected variant on the left and any selected variant on the right are also sufficiently separated because the anchor lies between them.

Hints

Show hint 1

For a proposed separation d, ask whether at least k variants can be selected while including the reference. How does feasibility change as d increases?

Show hint 2

Sort the variants by intensity. Starting at the reference, greedily accept the nearest eligible variant while moving left, and independently do the same while moving right.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you also return one optimal selection of original indices, in increasing index order?
  • How would the feasibility check change if two specified reference variants both had to be included?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem