Maximize the Minimum Gap in a Subsequence
Problem statement
You are given an array arr of distinct positive integers in any order (it is not necessarily sorted). Consider every subsequence of exactly m of its elements. For a chosen subsequence s, define its current minimum as the smallest absolute difference between any two of its elements:
$$\text{currentMinimum}(s) = \min_{x, y \in s,\, x \ne y} |x - y|.$$
Across all $\binom{n}{m}$ subsequences of size m, define the global maximum as the largest such current minimum:
$$\text{globalMaximum} = \max_{|s| = m} \text{currentMinimum}(s).$$
Return globalMaximum: the largest value g for which you can pick m elements so that every pair is at least g apart.
Complete:
def findMaximum(arr: list[int], m: int) -> int:
Constraints:
- $2 \le m \le n \le 10^5$
arrholds distinct positive integers in arbitrary order, values up to $10^9$.
Examples:
arr = [1, 2, 8, 4, 9],m = 3-> sorting gives[1, 2, 4, 8, 9]; picking[1, 4, 8]gives a minimum gap of3, and no choice of 3 elements does better, so the answer is3.arr = [1, 2, 3, 4],m = 3-> any 3 of these 4 values include two consecutive integers (for example[1, 3, 4]and[1, 2, 4]both have min gap1), so the answer is1.arr = [10, 20, 30],m = 2-> picking the two endpoints[10, 30]gives gap20, the answer is20.arr = [100, 1, 50],m = 3-> all three are chosen; sorted they are[1, 50, 100], so the answer is49.
Show hint
What kind of search works when you are asked for the largest value that still satisfies a yes/no condition?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.