Spread-Out Price Picks

Medium

You are given a list of prices prices and an integer count. Choose exactly count different positions from the list (different positions may hold the same price). The variety of a choice is the smallest absolute price difference over all pairs of chosen positions. Return the largest variety you can achieve.

Example 1

prices=[12, 3, 30, 7, 19], count=3 → 11

Take prices 3, 19 and 30: the pairwise differences are 16, 27 and 11, the smallest being 11. Nothing does better.

Example 2

prices=[5, 5, 9], count=2 → 4

Take 5 and 9, with a difference of 4.

Example 3

prices=[2, 2, 2], count=3 → 0

Constraints

2 ≤ count ≤ len(prices) ≤ 10⁵
1 ≤ prices[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Binary Search Sorting

Similar problems

Stick Triples That Form a Triangle Medium Best-Paid Gig for Each Worker Medium Prices That Fade With Each Sale Medium Even Out With Increments Medium Rug Over Painted Stretches Medium

Input

prices=[12, 3, 30, 7, 19], count=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.