Maximize the Minimum Gap in a Subsequence

Reported in interviews at Citadel

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$
  • arr holds 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 of 3, and no choice of 3 elements does better, so the answer is 3.
  • 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 gap 1), so the answer is 1.
  • arr = [10, 20, 30], m = 2 -> picking the two endpoints [10, 30] gives gap 20, the answer is 20.
  • arr = [100, 1, 50], m = 3 -> all three are chosen; sorted they are [1, 50, 100], so the answer is 49.
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.

Related free problems