Maximize the minimum difference between k elements

JavaView on GFG

Intuition

Select k elements to maximize the minimum gap between consecutive selected elements. Binary search + greedy.

Algorithm

1Sort. Binary search on minimum gap d. Greedy: greedily pick elements with at least d gap. If can pick k: d is feasible.

Common Pitfalls

•Same as LC 1870 / allocation problems. Sort, then binary search on gap, greedy feasibility check.

Maximize the minimum difference between k elements.java

Java

// Approach: Sort array. Binary search on minimum difference; check if we can pick k elements with that gap.
// Time: O(n log(max-min)) Space: O(1)
import java.util.*;

class Solution {
    public int maxMinDiff(int[] arr, int k) {
        Arrays.sort(arr);
        int low = 0, high = arr[arr.length - 1] - arr[0], ans = 0;
        while (low <= high) {
            int mid = (low + high) / 2, count = 1, last = arr[0];
            for (int i = 1; i < arr.length && count < k; i++) {
                if (arr[i] - last >= mid) {
                    count++;
                    last = arr[i];
                }
            }

            if (count >= k) {
                ans = mid;
                low = mid + 1;
            } else
                high = mid - 1;
        }
        
        return ans;
    }
}

Was this solution helpful?